Fibonacci Number 7

Interview

Time limit1sMemory limit512 MB

Summary

Compute the n-th Fibonacci number modulo 1,000,000,007 for n up to one million.

Level: Medium6 of 10
Topics: Dynamic programming, Math, Implementation
Solved: No attempts yet

Problem

The Fibonacci sequence starts with 0 and 1. The 0th Fibonacci number is 0 and the 1st Fibonacci number is 1. From the 2nd number on, each Fibonacci number is the sum of the two numbers directly before it.

As a formula, $F_n = F_{n-1} + F_{n-2}$ ( $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$ , write a program that finds the $n$ -th Fibonacci number.

Input

The first line contains $n$ . $n$ is 0 or a natural number at most 1,000,000.

Output

Print the $n$ -th Fibonacci number modulo 1,000,000,007 on the first line.

Examples2

Example 1
Input
```
10
```
Expected output
```
55
```
Example 2
Input
```
1000
```
Expected output
```
517691607
```