I. Modulo Permutations
time limit per test
1 s
memory limit per test
256 MB
input
standard input
output
standard output

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

Input

The only line of the input contains the integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

Output

Output a single integer — the number of the permutations satisfying the condition from the statement, modulo $$$10^9+7$$$.

Examples
Input
1
Output
1
Input
2
Output
2
Input
3
Output
6
Input
4
Output
16
Input
5
Output
40
Input
1000000
Output
581177467
Note

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 \gt 2$$$ which violates the condition from the statement.