#include<cstdio>
#include<cstring>
using namespace std;
inline int in(){
	int x=0,f=1;char c;
	c=getchar();
	while (c<'0'||c>'9'){
		if (c=='-')f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){x=(x<<4)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
const int mod=1e9+7;
int n,a[4][4],b[4][4],t[4][4],q;
inline void work(int x[4][4],int y[4][4]){
	memset(t,0,sizeof t);
	for (int i=1;i<=3;i++)
		for (int j=1;j<=3;j++)
			for (int k=1;k<=3;k++)
				t[i][j]=(t[i][j]+1ll*x[i][k]*y[k][j])%mod;
	memcpy(b,t,sizeof (t));
}
inline void ksm(int l){
	if (l==1){memcpy(b,a,sizeof (a));return ;}
	ksm(l>>1);
	work(b,b);
	if (l&1)work(b,a);
}
int main(){
	q=in();
	while (q--){
		memset(a,0,sizeof a);
		memset(b,0,sizeof b);
		a[1][1]=a[1][3]=a[2][1]=a[3][2]=1;
		b[1][1]=b[2][2]=b[3][3]=1;
		n=in();
		if (n<=3){puts("1");continue;}
		ksm(n);
		printf ("%d\n",b[2][1]);
	}
	return 0;
}