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

F(0) = 1

F(1) = 1

.............

F(i) = F(i-1) + F(i-2), i >= 2

Vậy 6 số Fibonacci đầu tiên của dãy là : 1 1 2 3 5 8

Yêu cầu: Cho số nguyên dương n (n ≤ 10¹⁸), tính T = F(n) mod (10⁹+7) (mod là phép chia lấy phần dư).

Dữ liệu vào: Một dòng duy nhất ghi số n.

Kết quả: Ghi ra kết quả T.

Giải thích: Số F(4) = 5. T= 5 mod (10⁹+7) =5

Ràng buộc:

• 60% số test ứng với 60% số điểm của bài toán có: 3 ≤ n ≤ 10².

• 20% số test ứng với 20% số điểm của bài toán có: 10² ≤ n ≤ 10⁸.

• 20% số test ứng với 20% số điểm của bài toán có: 10⁸ ≤ n ≤ 10¹⁸.