Problem Description

Calculate the total number of permutations of length $n$ consisting of numbers from $1$ to $n$, where for each permutation, the condition $p_i \bmod p_{i+1} \leq 2$ holds (with $p_{n+1} = p_1$), modulo $10^9 + 7$.

Input Format

A single integer $n\ (1 \leq n \leq 10^6)$.

Output Format

Output the answer modulo $10^9+7$.

Sample Input and Output

Sample Input #1

1

Sample Output #1

1

Sample Input #2

2

Sample Output #2

2

Sample Input #3

3

Sample Output #3

6

Sample Input #4

4

Sample Output #4

16

Sample Input #5

5

Sample Output #5

40

Sample Input #6

1000000

Sample Output #6

581177467

见题面 Input 部分

见题面 Output 部分