Determinants and GCD

Time limit2sMemory limit512 MB

Summary

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.

Level: Hard8 of 10
Topics: Math, Number theory, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

The entries of the $N \times N$ matrix $M$ are as follows.

$M(i, i) = 1$
$M(i, i+1) = 1$
$M(i, i-1) = -1$
every other entry is 0

For example, when $N = 4$ , $M$ is

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

Input

The first line contains $N$ . ( $1 \le N \le 100000$ )

Output

Print $S$ modulo $10^9+7$ . The $\gcd$ is computed from the actual determinant values, before any reduction modulo $10^9+7$ .

Examples5

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
2
```
Expected output
```
3
```
Example 3
Input
```
3
```
Expected output
```
5
```
Example 4
Input
```
4
```
Expected output
```
8
```
Example 5
Input
```
5
```
Expected output
```
13
```