#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1000000007;
struct Matrix{
    vector< vector<int> > x;
    inline int column() { return x.size(); }
    inline int row() { return x[1].size(); }
};
inline int read(){
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		w=(w<<1)+(w<<3)+(ch-48);
		ch=getchar();
	}
	return w*f;
}
inline Matrix time(Matrix a,Matrix b){
    //assert(a.column()==b.row());
    int x=a.row(),y=b.column(),z=a.column();
    Matrix ans;
    for(int i=1;i<=x;i++){
        for(int j=1;j<=y;j++){
            for(int k=1;k<=z;k++){
                ans.x[i][j]+=a.x[i][k]*b.x[k][j]%MOD;
                ans.x[i][j]%=MOD;
            }               
        }
    }
    return ans;
}
inline Matrix qpow(Matrix a,int b){
    assert(a.row()==a.column());
    int x=a.row();
    Matrix ans;
    for(int i=1;i<=x;i++) ans.x[i][i]=1;
    for(;b;b>>=1){
        if(b&1) ans=time(ans,a);
        a=time(a,a);
    }
    return ans;
}
signed main(){
    int T;
    T=read();
    while(T--){
        int n;
        n=read();
        Matrix a,b;
        b.x[1][1]=1;b.x[1][2]=1;b.x[1][3]=1;
        a.x[1][1]=1;a.x[1][2]=0;a.x[1][3]=1;
        a.x[2][1]=1;a.x[2][2]=0;a.x[2][3]=0;
        a.x[3][1]=0;a.x[3][2]=1;a.x[3][3]=0;
        a=qpow(a,n-1);
        b=time(b,a);
        printf("%lld\n",b.x[1][1]);
    }
    return 0;
}