Cho dãy số Fibonacci với F[0] = 1, F[1] = 1, F[n] = F[n - 1] + F[n - 2) với n>= 2. Hãy tính F[n) chia dư cho 10^9 + 7.

Đầu vào:

Dòng 1 là số bộ test T

T dòng tiếp theo mỗi dòng là 1 số nguyên không âm N

Ràng buộc:

1<=T<=10000

0<=N<=10^6

Đầu ra: Đưa ra kết quả của mỗi test trên 1 dòng

Input:

5
1
2
3
4
5

Output:

1
2
3
5
8