給定一個自然數 $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$，這違反了題目中的條件。