Dãy số Fibonacci được định nghĩa bởi công thức:

$$\left\{ \begin{array}{l}{F_0} = {F_1} = 1\\{F_n} = {F_{n - 1}} + {F_{n - 2}},\forall n \ge 2\end{array} \right.$$

Yêu cầu: Cho số nguyên không âm ~n~, hãy tính ~F_n~.

Input

• Một dòng duy nhất chứa số nguyên không âm ~n~.

Giới hạn:

• ~0 ≤ n ≤ 10^{18}~.

Output

• Một dòng duy nhất chứa số nguyên là phần dư của ~F_n~ khi chia cho ~10^9 + 7~.

Sample

Input #1

10

Output #1

89

Input #2

45

Output #2

836311896

Problem source: Chuyên Sơn La Online Judge