Sum of odd-indexed Fibonacci numbers

Time limit1sMemory limit256 MB

Summary

Given n up to 1e18, compute the sum of odd-indexed Fibonacci numbers from F_0 to F_n modulo 1,000,000,007.

Level: Medium5 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 and the 1st Fibonacci number is 1. From index 2 on, each Fibonacci number 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 as follows.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

Given $n$ , write a program that computes the sum of the Fibonacci numbers with an odd index, taken from the 0th through the $n$ th. That is the value of $F_1 + F_3 + F_5 + \cdots$ restricted to the terms whose index is at most $n$ .

Input

The first line contains $n$ . $n$ is a natural number less than or equal to 1,000,000,000,000,000,000.

Output

Print on the first line the sum of the Fibonacci numbers with an odd index, taken from the 0th through the $n$ th, modulo 1,000,000,007.

Examples2

Example 1
Input
```
7
```
Expected output
```
21
```
Example 2
Input
```
10
```
Expected output
```
55
```