Дано натуральное число $n$. Найдите количество перестановок $(p_1, p_2, \dots, p_n)$ чисел от $1$ до $n$ таких, что для каждого $i$ ($1 \le i \le n$) выполняется следующее свойство: $p_i \pmod{p_{i+1}} \le 2$, где $p_{n+1} = p_1$.

Так как это число может быть очень большим, выведите его по модулю $10^9 + 7$.

Входные данные

Единственная строка входных данных содержит целое число $n$ ($1 \le n \le 10^6$).

Выходные данные

Выведите единственное целое число — количество перестановок, удовлетворяющих условию задачи, по модулю $10^9 + 7$.

Примеры

Входные данные 1

1

Выходные данные 1

1

Входные данные 2

2

Выходные данные 2

2

Входные данные 3

3

Выходные данные 3

6

Входные данные 4

4

Выходные данные 4

16

Входные данные 5

5

Выходные данные 5

40

Входные данные 6

1000000

Выходные данные 6

581177467

Примечание

Например, для $n = 4$ следует учесть перестановку $[4, 2, 3, 1]$, так как $4 \pmod 2 = 0 \le 2$, $2 \pmod 3 = 2 \le 2$, $3 \pmod 1 = 0 \le 2$, $1 \pmod 4 = 1 \le 2$. Однако не следует учитывать перестановку $[3, 4, 1, 2]$, так как $3 \pmod 4 = 3 > 2$, что нарушает условие задачи.