| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 129 | 59 | 55 | 47.414% |
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
2
2
3
6
4
16
5
40
1000000
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.