cho.sh

행렬식과 GCD

정해진 규칙을 따르는 삼대각 행렬에서 D(k)를 k×k 행렬식이라 할 때, i=1부터 N까지 gcd(D(i), D(N))의 합을 1e9+7로 나눈 나머지를 구한다.

어려움8수학정수론동적 계획법조합론아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

크기가 N×NN \times N인 행렬 MM의 원소는 다음과 같다.

  • M(i,i)=1M(i, i) = 1
  • M(i,i+1)=1M(i, i+1) = 1
  • M(i,i−1)=−1M(i, i-1) = -1
  • 나머지 원소는 모두 0

예를 들어 N=4N = 4이면 MM은 다음과 같다.

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

같은 규칙으로 만든 크기 k×kk \times k 행렬의 행렬식을 D(k)D(k)라고 하자. NN이 주어졌을 때 S=∑i=1Ngcd⁡(D(i),D(N))S = \sum_{i=1}^{N} \gcd(D(i), D(N))을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 NN이 주어진다. (1≤N≤1000001 \le N \le 100000)

출력

SS를 109+710^9+7로 나눈 나머지를 출력한다. gcd⁡\gcd는 나머지를 취하기 전의 실제 행렬식 값으로 계산한다.