Câu 2 đề thi HSG L9 Yên Thành

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^5~).

Dữ liệu:

• 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ả:

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^9+7~).

Ví dụ

Input

5
5
2
3
6
1

Output

5
1
2
8
1