#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3;  //矩阵大小 
const int mod=1e9+7;
struct Matrix{
    ll m[maxn][maxn];  
    Matrix(){
        memset(m,0,sizeof(m));
    }
};
Matrix Multi(Matrix a,Matrix b){
    Matrix res;
    for(int i=0;i<maxn;i++){
        for(int j=0;j<maxn;j++){
            for(int k=0;k<maxn;k++){
                res.m[i][j]=(res.m[i][j]+ (a.m[i][k]%mod) *( b.m[k][j]%mod)%mod ) %mod;
            } 
        }
    }
    return res;
} 
Matrix fastm(Matrix a,ll num){
    Matrix res;
    res.m[0][0]=6;
    res.m[1][0]=4;
    res.m[2][0]=3;
    while(num){
        if(num&1){
            res=Multi(a,res);
        }
        a=Multi(a,a);
        num>>=1;
    }
    return res;
}
int ans[3]={3,4,6};
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        ll n;
        scanf("%lld",&n);
        if(n<=4){
            printf("%d\n",ans[n-2]);
        }else{
            Matrix a;
            a.m[0][0]=1;
            a.m[0][1]=0;
            a.m[0][2]=1;
            a.m[1][0]=1;
            a.m[1][1]=0;
            a.m[1][2]=0;
            a.m[2][0]=0;
            a.m[2][1]=1;
            a.m[2][2]=0;
            a=fastm(a,n-4);
            printf("%lld\n",a.m[0][0]);
        }
    }
    return 0;
}