Sum of Even-Indexed Fibonacci Numbers

Time limit1sMemory limit256 MB

Summary

Given n, add the Fibonacci numbers at even indices from 0 to n and print the sum modulo 1000000007.

Level: Medium5 of 10
Topics: Matrix, Math
Solved: No attempts yet

Problem

The Fibonacci numbers start with 0 and 1. The 0th Fibonacci number is 0 and the 1st is 1. From index 2 on, each Fibonacci number is the sum of the two before it.

Written as a formula, $F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$ .

The Fibonacci numbers up to $n = 17$ are:

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

Given $n$ , compute the sum of the Fibonacci numbers whose index is even, taken over indices 0 through $n$ .

Input

The first line contains $n$ , a positive integer no larger than $10^{18}$ .

Output

Print on the first line the sum of the Fibonacci numbers with an even index, over indices 0 through $n$ , modulo $1000000007$ .

Examples4

Example 1
Input
```
7
```
Expected output
```
12
```
Example 2
Input
```
10
```
Expected output
```
88
```
Example 3
Input
```
1
```
Expected output
```
0
```
Example 4
Input
```
2
```
Expected output
```
1
```