408345: GYM103102 I Modulo Permutations

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$$$.

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 \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.