시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 39 23 18 60.000%

문제

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

  • 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 ≤ 105)

출력

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

예제 입력 1

1

예제 출력 1

1

예제 입력 2

2

예제 출력 2

3

예제 입력 3

3

예제 출력 3

5

예제 입력 4

4

예제 출력 4

8

예제 입력 5

5

예제 출력 5

13

힌트

출처