- Time limit: 1.00 s
- Memory limit: 512 MB
The Fibonacci numbers can be defined as follows:
- F_0=0
- F_1=1
- F_n = F_{n-2}+F_{n-1}
Your task is to calculate the value of F_n for a given n.
Input
The only input line has an integer n.
Output
Print the value of F_n modulo 10^9+7.
Constraints
- 0 \le n \le 10^{18}
Example
Input:
10
Output:
55