Yêu cầu

Dãy số Fibonacci là dãy số được định nghĩa như sau:

$$ f(1)=1 $$

$$ f(2)=1 $$

$$ f(n)=f(n-1)+f(n-2)\quad (n\geq 3) $$

Cho số nguyên dương $n$, hãy tính số Fibonacci thứ $n$.

Kết quả có thể rất lớn nên được lấy dư với $10^9+7$.

Mô tả đầu vào

• Dòng đầu tiên chứa số nguyên $t$ là số lượng test case.
• $t$ dòng tiếp theo, mỗi dòng chứa một số nguyên dương $n$.

Ràng buộc

$$ 1\leq n\leq 10^6 $$

$$ 1\leq t\leq 10^4 $$

Mô tả đầu ra

Gồm $t$ dòng, mỗi dòng là số Fibonacci thứ $n$ tương ứng, sau khi lấy dư cho $10^9+7$.

Test case mẫu

Đầu vào mẫu 1

2
3
5

Đầu ra mẫu 1

2
5