Given a natural number , count the number of permutations (p_1, p_2, \ldots, p_n) of the numbers from to , such that for each (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 (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.
Example 1
Example 2
Example 3
Example 4
Example 5
Example 6
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.