The Fibonacci sequence is F(0)=0, F(1)=1, and F(k)=F(k-1)+F(k-2) for k>=2. Because the numbers grow quickly, output F(n) modulo 1000000007.
Input format
One line: a non-negative integer n.
Output format
One line: F(n) mod 1000000007.
Constraints
- 0 <= n <= 1000000