P10744 [SEERC 2020] Modulo Permutations

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

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

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

Translated by ChatGPT 5