cho.sh

Determinants and GCD

For a tridiagonal matrix with a fixed pattern, let D(k) be its k-by-k determinant and compute the sum of gcd(D(i), D(N)) for i from 1 to N, modulo 1e9+7.

Hard8MathNumber theoryDynamic programmingCombinatoricsNo attempts yetTime limit2sMemory limit512 MB

Problem

The entries of the N×NN \times N matrix MM are as follows.

  • 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
  • every other entry is 0

For example, when N=4N = 4, MM is

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

Let D(k)D(k) be the determinant of the k×kk \times k matrix built by the same rule. Given NN, write a program that computes S=∑i=1Ngcd⁡(D(i),D(N))S = \sum_{i=1}^{N} \gcd(D(i), D(N)).

Input

The first line contains NN. (1≤N≤1000001 \le N \le 100000)

Output

Print SS modulo 109+710^9+7. The gcd⁡\gcd is computed from the actual determinant values, before any reduction modulo 109+710^9+7.