다음과 같은 원소를 갖는 크기가 N×N인 행렬이 있다.</p>

• M(i, i) = 1
• M(i, i+1) = 1
• M(i, i-1) = -1
• 다른 값은 모두 0

예를 들어, 크기 N = 4인 경우 M은 다음과 같다.

1 1 0 0
-1 1 1 0
0 -1 1 1
0 0 -1 1

D(k)를 크기가 k×k인 행렬 M의 행렬식(Determinant)이라고 하자. N이 주어졌을 때, S = Σgcd(D(i), D(N)) (1 ≤ i ≤ N) 을 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 10⁵)

출력 형식

S를 10⁹+7로 나눈 나머지를 출력한다.

예제 입력 1

1

예제 출력 1

1

예제 입력 2

2

예제 출력 2

3

예제 입력 3

3

예제 출력 3

5

예제 입력 4

4

예제 출력 4

8

예제 입력 5

5

예제 출력 5

13