Fibonacci Sequence :
Difficulty Level : Easy
Submissions : 444
Asked In :
Marks :10
: 1 | : 1
The Fibonacci Sequence is a sequence that is governed by the following recurrence relation. $$$F(n)=F(n-1)+F(n-2)$$$. You are given an integer $$$n$$$. You have to print the $$$nth$$$ number in the fibonacci series. The output may be large so print the output module $$$1e9+7$$$.
Input
A single integer $$$n$$$ $$$(2\le n \le10^6)$$$
Output
A single integer, printing the $$$nth$$$ number from the Fibonacci series.
Examples
Input
4
Output
2
Input
25
Output
46368
Note
The third number in the Fibonacci series is 2
0 , 1 , 1 , 2 ....
