Modulo Permutations#12843

Modulo Permutations

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.

Input

The only line of the input contains the integer (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

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Example 4

Loading
Loading

Example 5

Loading
Loading

Example 6

Loading
Loading

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