给定一个自然数 $n$，计算从 $1$ 到 $n$ 的排列 $(p_1, p_2, \dots, p_n)$ 的数量，使得对于每个 $i$ ($1 \le i \le n$)，以下性质成立：$p_i \pmod{p_{i+1}} \le 2$，其中 $p_{n+1} = p_1$。

由于该数字可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

输入仅一行，包含一个整数 $n$ ($1 \le n \le 10^6$)。

输出格式

输出一个整数，即满足题目条件的排列数量，对 $10^9 + 7$ 取模。

样例

输入 1

1

输出 1

1

输入 2

2

输出 2

2

输入 3

3

输出 3

6

输入 4

4

输出 4

16

输入 5

5

输出 5

40

输入 6

1000000

输出 6

581177467

说明

例如，对于 $n = 4$，你应该统计排列 $[4, 2, 3, 1]$，因为 $4 \pmod 2 = 0 \le 2$，$2 \pmod 3 = 2 \le 2$，$3 \pmod 1 = 0 \le 2$，$1 \pmod 4 = 1 \le 2$。然而，你不应该统计排列 $[3, 4, 1, 2]$，因为 $3 \pmod 4 = 3 > 2$，这违反了题目中的条件。