Các số Fibonacci có thể được định nghĩa như sau:

• \(F_0 = 0\)
• \(F_1 = 1\)
• \(F_n = F_{n-2} + F_{n-1}\)

Nhiệm vụ của bạn là tính giá trị của \(F_n\) với \(n\) được cho.

Input

• Dòng đầu vào duy nhất có một số nguyên \(n\) \((0 \leq n \leq 10^{18})\).

Output

• In giá trị của \(F_n\) chia lấy dư cho \(10^9 + 7\).

Example

10

55