자연수 $n$이 주어졌을 때, $1$부터 $n$까지의 숫자로 이루어진 순열 $(p_1, p_2, \dots, p_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$이므로 문제의 조건을 위반하여 개수에 포함하지 않는다.