Cho một số tự nhiên $n$, hãy đếm số lượng hoán vị $(p_1, p_2, \dots, p_n)$ của các số từ $1$ đến $n$, sao cho với mỗi $i$ ($1 \le i \le n$), tính chất sau đây được thỏa mãn: $p_i \pmod{p_{i+1}} \le 2$, trong đó $p_{n+1} = p_1$.

Vì số lượng này có thể rất lớn, hãy in ra kết quả theo modulo $10^9 + 7$.

Dữ liệu vào

Dòng duy nhất của dữ liệu vào chứa số nguyên $n$ ($1 \le n \le 10^6$).

Dữ liệu ra

In ra một số nguyên duy nhất — số lượng các hoán vị thỏa mãn điều kiện từ đề bài, theo modulo $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

1

Dữ liệu ra 1

1

Dữ liệu vào 2

2

Dữ liệu ra 2

2

Dữ liệu vào 3

3

Dữ liệu ra 3

6

Dữ liệu vào 4

4

Dữ liệu ra 4

16

Dữ liệu vào 5

5

Dữ liệu ra 5

40

Dữ liệu vào 6

1000000

Dữ liệu ra 6

581177467

Ghi chú

Ví dụ, với $n = 4$, bạn cần đếm hoán vị $[4, 2, 3, 1]$, vì $4 \pmod 2 = 0 \le 2$, $2 \pmod 3 = 2 \le 2$, $3 \pmod 1 = 0 \le 2$, $1 \pmod 4 = 1 \le 2$. Tuy nhiên, bạn không nên đếm hoán vị $[3, 4, 1, 2]$, vì $3 \pmod 4 = 3 > 2$, điều này vi phạm điều kiện từ đề bài.