Modified Fibonacci Sequence

Given a non-negative integer ( n ), compute the ( n )-th term of the sequence defined by [ F(0) = 1,\quad F(1) = 1,\quad F(n) = F(n-1) + F(n-2) \quad \text{for } n \geq 2. ] Note that this sequence corresponds to the standard Fibonacci sequence shifted by one, i.e. ( F(n) = \text{Fib}(n+1) ), where ( \text{Fib}(0)=0 ) and ( \text{Fib}(1)=1 ). Since the answer can be very large, output the answer modulo (10^9+7).

inputFormat

A single non-negative integer ( n ) (e.g. (0 \le n \le 10^9)).

outputFormat

Output the ( n )-th term of the sequence modulo (10^9+7).

sample

0

1