#include <vector>
#include <iostream>
using namespace std;

typedef long long ll;
typedef vector<vector<ll> > matrix;
const ll MOD = 1000000007;
const int K = 2;

matrix mul(matrix A, matrix B)
{
    matrix C(K+1, vector<ll>(K+1));
   for (int i = 1; i <= K; i++)
   for (int j = 1; j <= K; j++)
   for (int k = 1; k <= K; k++)
        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}
matrix pow(matrix A, int p)
{
    if (p == 1)
        return A;
    if (p % 2)
        return mul(A, pow(A, p-1));
    matrix X = pow(A, p/2);
    return mul(X, X);
}

int fib(int n)
{

    vector<ll> F1(K+1);
    F1[1] = 1;
    F1[2] = 1;


    matrix T(K+1, vector<ll>(K+1));
    T[1][1] = 0, T[1][2] = 1;
    T[2][1] = 1, T[2][2] = 1;

    if (n == 1)
        return 1;
    T = pow(T, n-1);
    ll wynik = 0;
   for (int i = 1; i <= K; i++)
        wynik = (wynik + T[1][i] * F1[i]) % MOD;
    return wynik;

}
int main() {
	int a, n = 0;

	cin >> a;
	if(a<100){
	for(int i=0; i<a; i++)
	while (cin >> n){
	cout<< 	fib(n)<< endl;
	}
		}
	else return 0;
}