Fibonacci sequence is a recursive sequence that depends on the following definition:
Fib(N) = Fib(N-1) + Fib(N-2)
Fib(0) = 0
Fib(1) = 1
In this problem you have to calculate this simple function. Given N, you have to calculate Fib(N) modulo 1000000007.
Input contains a single line, N (1 ≤ N ≤ 109 ).
You have to print one line with the value of Fib(N) modulo 1000000007.
Input | Output |
---|---|
2 | 1 |