Fibonacci

Công thức số Fibonacci:

• ~F[0] = 1, F[1] = 1;~
• ~F[n] = F[n-1] + F[n-2]~ với ~i >= 2.~

Nhiệm vụ của bạn là hãy tìm số Fibonacci thứ n.

Input

Dòng đầu tiên là số lượng bộ test ~ T (T <= 20)~.

Mỗi test bắt đầu bởi số nguyên dương ~N (N <= 10^{15})~.

Output

Với mỗi test, in ra đáp án tìm được theo modulo ~10^9 + 7~.

Sample Input 1

3
5
6
19

Sample Output 1

8
13
6765