Các số Fibonacci đượ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~ cho trước.

Dữ liệu vào

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

Kết quả

In ra giá trị của ~F\_n~ modulo ~10^9+7~.

Giới hạn

• ~0 \le n \le 10^{18}~

Ví dụ

Dữ liệu vào:

10

Kết quả:

55