Problem Description

Count the number of all permutations of $1 \sim n$ of length $n$ that satisfy $p_i \bmod p_{i+1} \leq 2$ (where $p_{n+1} = p_1$), and output the result modulo $10^9 + 7$.

Input Format

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

Output Format

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

1

1

2

2

3

6

4

16

5

40

1000000

581177467

Hint

Translated by ChatGPT 5