#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL mod = 1e9+7;

struct Matrix{

    LL a[3][3];

    void set1(){

        memset(a, 0, sizeof(a));

    }

    void set2(){

        memset(a, 0, sizeof(a));

        for(int i=0; i<3; i++) a[i][i]=1;

    }

    void set3()

    {

        a[0][0]=4,a[0][1]=17,a[0][2]=-12;

        a[1][0]=1,a[1][1]=0,a[1][2]=0;

        a[2][0]=0,a[2][1]=1,a[2][2]=0;

    }

};

Matrix operator * (const Matrix &a, const Matrix &b){

    Matrix res;

    res.set1();

    for(int i=0; i<3; i++){

        for(int j=0; j<3; j++){

            for(int k=0; k<3; k++){

                res.a[i][j] = (res.a[i][j]%mod+a.a[i][k]*b.a[k][j]%mod + mod)%mod;

            }

        }

    }

    return res;

}

Matrix qsm(Matrix a, LL n){

    Matrix res;

    res.set2();

    while(n){

        if(n&1) res = res*a;

        a = a*a;

        n/=2LL;

    }

    return res;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        LL n;

        scanf("%lld", &n);

        if(n==2){

            puts("31");

        }

        else if(n==3){

            puts("197");

        }

        else if(n==4){

            puts("1255");

        }

        else{

            Matrix A,B;

            A.set3();

            B = qsm(A, n-4);

            LL ans = (B.a[0][0]*1255%mod+B.a[0][1]*197%mod+B.a[0][2]*31%mod+mod)%mod;

            printf("%lld\n", ans%mod);

        }

    }

    return 0;

}