Xét dãy số Fibonaci {F_n} theo định nghĩa:

F₁ = F₂ = 1

F_n = F_{n - 1} + F_{n - 2} với mọi n > 2

Cho n, hãy tính F_n và đưa ra số dư của F_n chia cho (10⁶ + 7)

Dữ liệu vào: n (0 < n ≤ 10⁶)

Dữ liệu ra: một số nguyên – số dư tìm được.