THỰC HÀNH

Dãy số Fibonacci được định nghĩa bởi công thức:

Yêu cầu: Cho số nguyên không âm n, hãy tính F_n.

Dữ liệu vào:

Một dòng duy nhất chứa số nguyên không âm n.

Dữ liệu ra:

Một dòng duy nhất chứa số nguyên là phần dư của F_n khi chia cho 10⁹ + 7.

Ví dụ:

Dữ liệu vào:
10

Dữ liệu ra:
89

Dữ liệu vào:
45

Dữ liệu ra:
836311896

Giới hạn: 0 ≤ n ≤ 10¹⁸.