Sum of Squares of Fibonacci Numbers

Time limit1sMemory limit256 MB

Summary

Read n up to 1e18 and print the sum of squared Fibonacci numbers F_0 through F_n modulo 1,000,000,007.

Level: Medium6 of 10
Topics: Math, Matrix, Divide and conquer
Solved: No attempts yet

Problem

The Fibonacci numbers start with 0 and 1. The 0th Fibonacci number is 0, the 1st is 1, and from the 2nd on each one is the sum of the two before it. As a formula, $F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$ .

Written out up to $n = 17$ , the Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597.

Given $n$ , write a program that adds up the squares of the Fibonacci numbers from the 0th through the $n$ th.

Input

The first line contains $n$ . It is a natural number between 1 and 1,000,000,000,000,000,000, inclusive.

Output

Print $F_0^2 + F_1^2 + \cdots + F_n^2$ modulo 1,000,000,007 on the first line.

Examples2

Example 1
Input
```
10
```
Expected output
```
4895
```
Example 2
Input
```
1
```
Expected output
```
1
```