quantum is not feeling well today, and has decided to create a more painful version of the simple Fibonacci problem.

Recall that the Fibonacci sequence is a well known sequence of numbers in which

$${\displaystyle F(n)=\{\begin{array}{ll}0,& \text{if }n=0\\ 1,& \text{if }n=1\\ F(n-2)+F(n-1),& \text{if }n\ge 2\end{array}}$$

You are given a number $N$ $(1\le N\le {10}^{100000})$, find the $N^{th}$ Fibonacci number, modulo $1000000007$ $(={10}^9+7)$.

Input Specification

The first line of input will have the number $N$.

Output Specification

The $N^{th}$ Fibonacci number, modulo $1000000007$ $(={10}^9+7)$.

Sample Input

26

Sample Output

121393