Bài 2. (5 điểm) Fibonacci

Dãy số Fibonacci được Fiboncci, một nhà toán học người Ý, công bố vào năm 1202 trong cuốn sách Liber Abacci - Sách về toán đố qua 2 bài toán: Bài toán con thỏ và bài toán các số “cụ tổ” của một ong đực. Dãy số số Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1 hoặc 1 và 1, các phần tử sau đó thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Công thức F1 = F2 = 1, Fn= F(n-1) + F(n-2) với mọi số nguyên n lớn hơn 2. Ta có thể liệt kê một số phần tử đầu tiên như sau: 1, 1, 2, 3, 5, 8, 13, 21,

Yêu cầu: Cho T câu hỏi, mỗi câu là một số N. Hãy viết chương trình số fibo thứ N trong đó (N, T<=10⁵).

Dữ liệu: vào từ file FIBO.INP có cấu trúc:

- Dòng 1 chứa số nguyên dương T

- T dòng tiếp theo, mỗi dòng là một số nguyên dương N.

Kết quả: ghi file FIBO.OUT cấu trúc sau:

In ra T dòng, mỗi dòng là một số Fibo F(n). Vì dữ liệu bài này rất lớn, nên hãy in ra kết quả chia lấy dư (10⁹+7).