Số Fibonacci

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

• $$F_0=0,F_1=1,F_n=F_{n-2}+F_{n-1}$$

Cho $n$, tính giá trị $F_n$ modulo ${10}^9+7$.

Dữ liệu vào

Một dòng chứa số nguyên $n$.

Dữ liệu ra

In giá trị $F_n$ modulo ${10}^9+7$.

Ràng buộc

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

Ví dụ