#include <bits/stdc++.h>
#define modd 1000000007
using namespace std;
int n, k, t;

struct mat {
	int matrix[5][5];

} a, ans;

mat operator*(const mat &x, const mat &y) {
	mat f;
	memset(f.matrix, 0, sizeof(f.matrix));
	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			for(int k = 0; k < 3; k++) {
				f.matrix[i][j]+=(x.matrix[i][k]%modd)*(y.matrix[k][j]%modd);
				f.matrix[i][j]%=modd;
			}
	return f;
}

void shit()
{
	memset(ans.matrix, 0,sizeof(ans.matrix));
	memset(a.matrix, 0, sizeof(a.matrix));
	for(int i = 0; i < 3; i++)
	{
		ans.matrix[i][i]=1;
	}
	a.matrix[0][0]=a.matrix[0][2]=a.matrix[1][0]=a.matrix[2][1]=1;
}

signed main() {
	cin >> t;
	while(t--)
	{
		cin >> n;
		if(n<=3)
		{
			cout << 1;
			continue;
		}
		shit();
			
		while(n)
		{
			if(n&1)
			{
				ans=ans*a;
				
			}
			a=a*a;
			n/=2;
		}
		cout << ans.matrix[1][0] << endl;
		
	}
	return 0;
}