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\).

Output

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

Constraints

• \(0 \le n \le 10^{18}\)

Example

Sample input

10

Sample output

55