시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 79 | 38 | 36 | 51.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
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.