Given a natural number n, count the number of permutations (p[1]
, p[2]
, ..., p[n]
) of the numbers from 1 to n, such that for each i (1 ≤ i ≤ n), the following property holds: p[i]
mod p[i+1]
≤ 2, where p[n+1]
= p[1]
.
As this number can be very big, output it modulo 10^9
+ 7.
One integer n (1 ≤ n ≤ 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 [4, 2, 3, 1] as 4 mod 2 = 0 ≤ 2, 2 mod 3 = 2 ≤ 2, 3 mod 1 = 0 ≤ 2, 1 mod 4 = 1 ≤ 2. However, you shouldn’t count the permutation [3, 4, 1, 2], as 3 mod 4 = 3 > 2 which violates the condition from the statement.