Dãy số Fibonacci được Fibonacci, 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 số các "cụ tổ" của một ong đực. Dãy 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 đó được 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 truy hồi của dãy Fibonacci là:

Yêu cầu:

Cho Q câu hỏi, mỗi câu hỏi là một số N. Hãy viết chương trình tính số fibo thứ N.

Giới hạn: N , Q <= \(10^5\)

Dữ liệu vào:

• Dòng đầu tiên nhập vào số nguyên dương Q.

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

Kết quả:

• In ra Q dòng, mỗi dòng là một số fibo tương ứng với truy vấn nhập vào. 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^9\) + 7).