自然数 $n$ が与えられる。$1$ から $n$ までの数の順列 $(p_1, p_2, \dots, p_n)$ のうち、各 $i$ ($1 \le i \le n$) に対して以下の性質を満たすものの個数を求めよ。ただし、$p_{n+1} = p_1$ とする。

$$p_i \pmod{p_{i+1}} \le 2$$

この数は非常に大きくなる可能性があるため、$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$ となり、問題文の条件に違反するため数えてはならない。