#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const long long MOD=1e9+7;

struct matrix
{
    long long t[4][4];

    matrix()
    {
        memset(t,0LL,sizeof(t));
    }
    friend inline matrix operator* (const matrix &a, const matrix &b)
    {
        matrix c=matrix();
        for(int i=0; i<4; i++)
            for(int j=0; j<4; j++)
                for(int k=0; k<4; k++)
                    c.t[i][j]=(c.t[i][j]+a.t[i][k]*b.t[k][j])%MOD;
        return c;
    }
};

long long n;
long long a[4]={1,0,2,1};
long long b[4]={0,1,1,1};
matrix m;

matrix fastPow(matrix X,long long pw)
{
    matrix res;
    for(int i=0; i<4; i++)
    {
        res.t[i][i]=1;
    }
    while(pw>0)
    {
        if(pw%2) res=res*X;
        pw/=2;
        X=X*X;
    }
    return res;
}

void init()
{
    m.t[0][0]=m.t[0][1]=m.t[0][2]=0; m.t[0][3]=-1;
    m.t[1][0]=1; m.t[1][1]=m.t[1][2]=0; m.t[1][3]=1;
    m.t[2][0]=0; m.t[2][1]=1; m.t[2][2]=0; m.t[2][3]=2;
    m.t[3][0]=m.t[3][1]=0; m.t[3][2]=1; m.t[3][3]=0;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

freopen("penguin.in","r",stdin);
freopen("penguin.out","w",stdout);

int tt;
cin>>tt;
while(tt--)
{
    cin>>n; init();

    if(n<=4)
    {
        cout<<(a[n-1]+b[n-1])%MOD<<endl;
        continue;
    }

    matrix cur=fastPow(m, n-4);
    long long A=0;
    long long B=0;
    for(int i=0;i<4;i++)
    {
        A+=a[i]*cur.t[i][3]%MOD;
        B+=b[i]*cur.t[i][3]%MOD;
    }
    A+=10*MOD;
    B+=10*MOD;

    cout<<(A+B)%MOD<<endl;
}

return 0;
}