Even more sequences of bits P84293

Please compute the number of different sequences of length $n$, made up of only zeroes and ones, and with no more than two consecutive ones.

Input

Input consists of several cases, each with a natural number $n$ between 0 and $10^9$.

Output

For every case, print the number of different sequences of $n$ bits that do not have more than two consecutive ones, modulo $10^9 + 7$.

Hint

A matrix can be powered to a natural number $x$ with only $\Theta(\log x)$ products of matrices.