#include<cstring>
#define mod 1000000007
#define ll long long
#define int long long
#define N 105
struct Matrix{
	ll matrix[N][N];
	Matrix(){memset(matrix,0,sizeof(matrix));}
	void buildMatrix(){memset(matrix,0,sizeof(matrix));}
}base,result;
Matrix operator*(const Matrix &A,const Matrix &B){
	Matrix C;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
            for(int k=1;k<=3;k++)
			C.matrix[i][j]+=(A.matrix[i][k]%mod)*(B.matrix[k][j]%mod),C.matrix[i][j]%=mod;
		}
	}
	return C;
}
void Matrix_quickPower(int value){
    while(value){
        if(value&1)result=result*base;
        base=base*base;
        value>>=1;
    }
}
signed main(){
    std::ios::sync_with_stdio(0);
    int T;
    std::cin>>T;
    while(T--){
        int n;
        std::cin>>n;
        if(n<=3)puts("1");
        else{
            memset(result.matrix,0,sizeof(result.matrix));
            for(int i=1;i<=3;i++)
                result.matrix[i][i]=1;
            memset(base.matrix,0,sizeof(base.matrix));
            base.matrix[1][1]=base.matrix[1][3]=base.matrix[2][1]=base.matrix[3][2]=1;
            Matrix_quickPower(n);
            std::cout<<result.matrix[2][1]<<std::endl;
        }
    }
}