408345: GYM103102 I Modulo Permutations
Description
Given a natural number $$$n$$$, count the number of permutations $$$(p_1, p_2, \ldots, 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 \text{ 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$$$.
InputThe only line of the input contains the integer $$$n$$$ ($$$1 \le n \le 10^6$$$).
OutputOutput a single integer — the number of the permutations satisfying the condition from the statement, modulo $$$10^9+7$$$.
ExamplesInput1Output
1Input
2Output
2Input
3Output
6Input
4Output
16Input
5Output
40Input
1000000Output
581177467Note
For example, for $$$n = 4$$$ you should count the permutation $$$[4, 2, 3, 1]$$$, as $$$4 \text{ mod } 2 = 0 \leq 2$$$, $$$2 \text{ mod } 3 = 2 \leq 2$$$, $$$3 \text{ mod } 1 = 0 \leq 2$$$, $$$1 \text{ mod } 4 = 1 \leq 2$$$. However, you shouldn't count the permutation $$$[3, 4, 1, 2]$$$, as $$$3 \text{ mod } 4 = 3 > 2$$$ which violates the condition from the statement.