Pondo Fibonacci

Problem Statement

Pondo would like to know the $n^{th}$ Fibonacci number modulo $10^9+7$. The $n^{th}$ Fibonacci number is determined by the following recurrence $f(n) = f(n - 1) + f(n - 2)$ and $f(1) = 1, f(0) = 0$.

Input Format

Your first line of input will contain a single integer $n$.

Output Format

Output a single integer representing the $n^{th}$ Fibonacci number modulo $10^9+7$.

Constraints

• $1 \leq n \leq 10^9$

Sample Cases

10

55

1000000000

21

Explanation 2

Remember to modulo.

99999999

36891058