행렬식과 GCD

크기가 $N \times N$인 행렬 $M$의 원소는 다음과 같다.

• $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

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

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

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