#include<bits/stdc++.h>
#define int long long
using namespace std;
int f[100000];
const int mod=1e9+7;
int I[4][4],ans[2][4],c[4][4];
void jz(int a[][4],int b[][4]){
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			for(int l=1;l<=3;l++){
				c[i][j]+=a[i][l]*b[l][j];
				c[i][j]=(c[i][j]+mod)%mod;
			}
		}
	}
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			a[i][j]=c[i][j];
			c[i][j]=0;
		}
	}
}
signed main(){
	I[1][1]=1,I[2][1]=1,I[1][3]=1,I[3][2]=1;
	ans[1][1]=1,ans[1][2]=1,ans[1][3]=1;
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int k=n-1;
		while(k){
			if(k&1){
				jz(ans,I);
			}
			jz(I,I);
			k=k>>1;
		}
		cout<<ans[1][1]<<"\n";
	}
	return 0;
}