Recursion [I]

The Fibonacci Sequence is a famous sequence defined by the recurrence relation:

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

For example, $F(0),F(1),F(2),F(3),F(4)$ can be written as $1,1,2,3,5$

In this question, you must compute $F(n)$ for some value $n$. Since the value may be quite large, output your answer modulo ${10}^9+7$.

Input

Input will contain a single integer $n$

Output

Output should contain a single integer, representing $F(n)\text{mod}{10}^9+7$.

Constraints

• $0\le n\le {10}^{1}8$

Example

Input

5

Output

8