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.