Étant donné un nombre naturel $n$, comptez le nombre de permutations $(p_1, p_2, \dots, p_n)$ des nombres de $1$ à $n$, telles que pour chaque $i$ ($1 \le i \le n$), la propriété suivante soit vérifiée : $p_i \pmod{p_{i+1}} \le 2$, où $p_{n+1} = p_1$.

Comme ce nombre peut être très grand, donnez le résultat modulo $10^9 + 7$.

Entrée

La seule ligne de l'entrée contient l'entier $n$ ($1 \le n \le 10^6$).

Sortie

Affichez un seul entier — le nombre de permutations satisfaisant la condition de l'énoncé, modulo $10^9 + 7$.

Exemples

Entrée 1

1

Sortie 1

1

Entrée 2

2

Sortie 2

2

Entrée 3

3

Sortie 3

6

Entrée 4

4

Sortie 4

16

Entrée 5

5

Sortie 5

40

Entrée 6

1000000

Sortie 6

581177467

Remarque

Par exemple, pour $n = 4$, vous devez compter la permutation $[4, 2, 3, 1]$, car $4 \pmod 2 = 0 \le 2$, $2 \pmod 3 = 2 \le 2$, $3 \pmod 1 = 0 \le 2$, $1 \pmod 4 = 1 \le 2$. Cependant, vous ne devez pas compter la permutation $[3, 4, 1, 2]$, car $3 \pmod 4 = 3 > 2$, ce qui viole la condition de l'énoncé.