Yêu cầu: Dãy số fibonacci là một dãy số hoàn toàn quen thuộc đối với chúng ta với quy luật như sau: F1=F2=1; Fn=Fn−1+Fn−2,∀ n ≥ 3 .
Hãy in số thì fibonacci thứ n ( n <= 10¹² ) trong dãy fibonacci nói trên (code bằng đệ quy). Kết quả có thể rất lớn nên ta chia lấy dư cho 10⁹+7 khi in ra.

Dữ liệu:
- Dòng đầu là số T với T test ( T <= 100),
- T dòng tiếp theo nhập vào số n( n <= 10¹² ).
Kết quả:
- Gồm T dòng tương ứng với mỗi đáp án trên.