Modulo Permutations

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 10^9 + 7.

Input

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

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