시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB79383651.429%

문제

Given a natural number $n$, count the number of permutations $(p_1, p_2, \dots , p_n)$ of the numbers from $1$ to $n$, such that for each $i$ ($1 \le i \le n$), the following property holds: $p_i \bmod p_{i+1} \le 2$, where $p_{n+1} = p_1$.

As this number can be very big, output it modulo $10^9 + 7$.

입력

The only line of the input contains the integer $n$ ($1 \le n \le 10^6$).

출력

Output a single integer — the number of the permutations satisfying the condition from the statement, modulo $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

힌트

For example, for $n = 4$ you should count the permutation $[4, 2, 3, 1]$, as $4 \bmod 2 = 0 \le 2$, $2 \bmod 3 = 2 \le 2$, $3 \bmod 1 = 0 \le 2$, $1 \bmod 4 = 1 \le 2$. However, you shouldn’t count the permutation $[3, 4, 1, 2]$, as $3 \bmod 4 = 3 > 2$ which violates the condition from the statement.