Dãy Fibonacci được định nghĩa như sau:

• ( F(0) = 1 )
• ( F(1) = 1 )
• ( F(i) = F(i-1) + F(i-2), $$\begin{gathered} i\ge 2 \\ ) \end{gathered}$$

Yêu cầu:

Cho số nguyên dương $$\begin{gathered} (n(n\le {10}^{18}) \\ ),tính \\ (F(n)\mathrm{mod}({10}^9+7) \\ ) \end{gathered}$$.

Input:

• Một dòng duy nhất ghi số ( N ).

Output:

• Ghi ra kết quả $$\begin{gathered} (F(n)\mathrm{mod}({10}^9+7) \\ ) \end{gathered}$$.