Modulo Permutations

Given a natural number n, count the number of permutations (p[1], p[2], ..., p[n]) of the numbers from 1 to n, such that for each i (1 ≤ i ≤ n), the following property holds: p[i] mod p[i+1] ≤ 2, where p[n+1] = p[1].

As this number can be very big, output it modulo 10^9 + 7.

Input

One integer n (1 ≤ n ≤ 10^6).

Output

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

Example

For example, for n = 4 you should count the permutation [4, 2, 3, 1] as 4 mod 2 = 0 ≤ 2, 2 mod 3 = 2 ≤ 2, 3 mod 1 = 0 ≤ 2, 1 mod 4 = 1 ≤ 2. However, you shouldn’t count the permutation [3, 4, 1, 2], as 3 mod 4 = 3 > 2 which violates the condition from the statement.

Examples