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

F₀ = 0

F₁ = 1

Fₙ = Fₙ₋₂ + Fₙ₋₁ (với n ≥ 2)

Nhiệm vụ của bạn là tính giá trị của Fₙ với một số nguyên n được cho trước.

Dữ liệu vào:

Dòng duy nhất chứa một số nguyên n.

Dữ liệu ra:

In ra giá trị Fₙ lấy modulo 10^9 + 7.

Ràng buộc:

0 ≤ n ≤ 10^18

Ví dụ :

Input:

10

Output:

55