Dla danej liczby naturalnej $n$ oblicz liczbę permutacji $(p_1, p_2, \dots, p_n)$ liczb od $1$ do $n$, takich że dla każdego $i$ ($1 \le i \le n$) spełniony jest następujący warunek: $p_i \pmod{p_{i+1}} \le 2$, gdzie $p_{n+1} = p_1$.

Ponieważ liczba ta może być bardzo duża, wyprowadź ją modulo $10^9 + 7$.

Wejście

Jedyna linia wejścia zawiera liczbę całkowitą $n$ ($1 \le n \le 10^6$).

Wyjście

Wyprowadź pojedynczą liczbę całkowitą — liczbę permutacji spełniających warunek z treści zadania, modulo $10^9 + 7$.

Przykład

Wejście 1

1

Wyjście 1

1

Wejście 2

2

Wyjście 2

2

Wejście 3

3

Wyjście 3

6

Wejście 4

4

Wyjście 4

16

Wejście 5

5

Wyjście 5

40

Wejście 6

1000000

Wyjście 6

581177467

Uwagi

Na przykład dla $n = 4$ należy policzyć permutację $[4, 2, 3, 1]$, ponieważ $4 \pmod 2 = 0 \le 2$, $2 \pmod 3 = 2 \le 2$, $3 \pmod 1 = 0 \le 2$, $1 \pmod 4 = 1 \le 2$. Jednakże nie należy liczyć permutacji $[3, 4, 1, 2]$, ponieważ $3 \pmod 4 = 3 > 2$, co narusza warunek z treści zadania.