Large Fibonacci Number Modulo

Interview

Time limit1sMemory limit256 MB

Summary

Given n up to 10^18, print the nth Fibonacci number modulo 1,000,000,007.

Level: Medium4 of 10
Topics: Matrix, Divide and conquer, Math
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 the 2nd one on, each Fibonacci number is the sum of the two that come right before it.

As a formula, $F_n = F_{n-1} + F_{n-2}$ ( $n \ge 2$ ).

Listing the Fibonacci numbers up to $n = 17$ gives:

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 $n$ th Fibonacci number.

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 the remainder of the $n$ th Fibonacci number divided by 1,000,000,007 on the first line.

Examples3

Example 1
Input
```
1000
```
Expected output
```
517691607
```
Example 2
Input
```
1
```
Expected output
```
1
```
Example 3
Input
```
17
```
Expected output
```
1597
```