Untitled

#include<bits/stdc++.h>
using namespace std;
long long mod=1e15+7;
long long n;
long long a[5][5],b[5][5],goc[5][5];
void nhan(long long x[5][5],long long y[5][5]){
	long long tam[5][5];
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			long long res=0;
			for(int k=1;k<=4;k++){
				res = res + (x[i][k]%mod * y[k][j]%mod)%mod;
				res = res % mod;
			}
			tam[i][j]=res;
		}
	}
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			a[i][j]=tam[i][j];
		}
	}
}
void lt(long long x){
	if(x==1) return;
	lt(x/2);
	nhan(a,a);
	if(x%2==1) nhan(a,b);
}
int main(){
	int tc;
	cin >> tc;
	while(tc--){
		cin >> n;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(goc,0,sizeof(goc));
		a[1][1]=1, a[1][2]=1 ,a[1][3]=1,a[1][4]=1;
		a[2][2]=1, a[2][3]=1, a[2][4]=1;
		a[3][2]=1, a[4][3]=1;
		b[1][1]=1, b[1][2]=1 ,b[1][3]=1,b[1][4]=1;
		b[2][2]=1, b[2][3]=1, b[2][4]=1;
		b[3][2]=1, b[4][3]=1;
		goc[1][1]=6,goc[2][1]=3,goc[3][1]=2,goc[4][1]=1;
		if(n==0) cout << "0" << endl;
		if(n==1) cout << "1" << endl;
		if(n==2) cout << "3" << endl;
		if(n==3) cout << "6" << endl;
		if(n>3){
			lt(n-3);
			nhan(a,goc);
			cout << a[1][1] << endl;
		}
	}
	return 0;
}