Mystery of Fibonacci

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

Input contains a single line, N (1 ≤ N ≤ 109 ).

Output

You have to print one line with the value of Fib(N) modulo 1000000007.

Sample

2

1