#include<bits/stdc++.h>
using namespace std;
const int md=1e9+7;
long long a[4][4],ans[4]={0,1,1,1},base[4][4],bj1[4][4],bj2[4][4];
void work1(){
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			bj2[i][j]=bj1[i][j];
			bj1[i][j]=0;
		}
	}
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			for(int k=1;k<=3;k++){
				bj1[i][j]+=base[i][k]*bj2[k][j]%md;
			}
		}
	}
}
void work2(){
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			bj2[i][j]=base[i][j];
			base[i][j]=0;
		}
	}
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			for(int k=1;k<=3;k++){
				base[i][j]+=bj2[i][k]*bj2[k][j]%md;
			}
		}
	}
}
void nul(int n){
	while(n){
		if(n%2==1){
			work1();
		}
		work2();
		n/=2;
	}
}
int main()
{
	long long n;
	int t;
	scanf("%d",&t);
	a[1][1]=1;
	a[1][3]=1;
	a[2][1]=1;
	a[3][2]=1;
	while(t){
		t--;
		scanf("%lld",&n);
		for(int i=1;i<=3;i++){
			for(int j=1;j<=3;j++){
				base[i][j]=a[i][j];
				bj1[i][j]=1;
				bj2[i][j]=0;
			}
		}
		nul(n-5);
		long long da=0;
		for(int i=1;i<=3;i++){
			da+=ans[i]*bj1[i][1];
			da%=md;
		}
		printf("%lld\n",da);
	}
	return 0;
}