#include<bits/stdc++.h>
#define int long long
using namespace std;
int const N=1e2+5,mod=1e9+7;
struct mat{
	int mt[N][N];
	int h,l;
	mat() {h=l=0; memset(mt,0,sizeof(mt));}
	mat operator *(const mat &tmp) const{
		mat c;
		c.h=h,c.l=tmp.l;
		for(int i=1;i<=h;i++){
			for(int j=1;j<=tmp.l;j++){
				for(int k=1;k<=l;k++){
					c.mt[i][j]+=mt[i][k]*tmp.mt[k][j];
					c.mt[i][j]%=mod;
				}
			}
		}
		return c;
	}
};
mat qp(mat x,int y){
	mat ans,base=x;
	ans.h=ans.l=x.l;
	for(int i=1;i<=ans.l;i++)
		ans.mt[i][i]=1;
	while(y){
		if(y&1)
			ans=ans*base;
		base=base*base;
		y>>=1;
	}
	return ans;
}
void print(mat o){
	for(int i=1;i<=o.h;i++){
		for(int j=1;j<=o.l;j++){
			cout<<o.mt[i][j]<<" ";
		}
		cout<<"\n";
	}
}
int n,p;
mat a,in;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	in.l=1,in.h=3;
	in.mt[1][1]=1;//递推矩阵，按照第一篇题解一样的递推方式，但是我没有定义2,3项的值为什么能正确？AC了
	a.l=a.h=3;
	a.mt[1][1]=a.mt[1][3]=a.mt[2][1]=a.mt[3][2]=1;
	cin>>p;
	while(p--){
		cin>>n;
		mat res=in*qp(a,n-1);
		cout<<res.mt[1][1]<<"\n";
	}
	return 0;
}