Modulo Permutations#10888
Given a natural number , count the number of permutations (p_1, p_2, ..., p_n) of the numbers from to , such that for each (1 \le i \le n), the following property holds: p_i \mod p_{i+1} \le 2, where p_{n+1} = p_1.
As this number can be very big, output it modulo 10^9 + 7.
One integer (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.
For example, for n = 4 you should count the permutation [, , , ] as 4 \mod 2 = 0 \le 2, 2 \mod 3 = 2 \le 2, 3 \mod 1 = 0 \le 2, 1 \mod 4 = 1 \le 2. However, you shouldn't count the permutation [, , , ], as 3 \mod 4 = 3 > 2 which violates the condition from the statement.
Example 1
Example 2
Example 3
Example 4
Example 5
Example 6