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

As this number can be very big, output it modulo 109 + 7.

Input

One integer n (1 ≤ n ≤ 106).

Output

Output a single integer - the number of the permutations satisfying the condition from the statement, modulo 109 + 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.