#include <bits/stdc++.h>using namespace std;const long long mod=1e9+7;const long long inf=1e18;int T;long long n;struct Matrix{    long long A[5][5];    int R, C;    Matrix operator*(Matrix b);};Matrix X, Y, Z;Matrix Matrix::operator*(Matrix b){    Matrix c;    memset(c.A, 0, sizeof(c.A));    int i, j, k;    for (i = 1; i <= R; i++)        for (j = 1; j <= C; j++)            for (k = 1; k <= C; k++)                c.A[i][j] = (c.A[i][j] + (A[i][k] * b.A[k][j])%mod)%mod;    c.R=R; c.C=b.C;    return c;}void init(){    n = n - 2;    memset(X.A,0,sizeof X.A);    memset(Y.A,0,sizeof Y.A);    memset(Z.A,0,sizeof Z.A);    Z.R = 1; Z.C = 3;    Z.A[1][1]=1; Z.A[1][2]=1; Z.A[1][3]=1;    for(int i=1;i<=3;i++) Y.A[i][i]=1; Y.R = 3; Y.C = 3;    X.A[1][1]=1; X.A[1][2]=0; X.A[1][3]=1;    X.A[2][1]=1; X.A[2][2]=0; X.A[2][3]=0;    X.A[3][1]=0; X.A[3][2]=1; X.A[3][3]=0;    X.R = 3; X.C = 3;}void work(){    while (n)    {        if (n % 2 == 1) Y = Y*X;        n = n >> 1;        X = X*X;    }    Z = Z*Y;    printf("%lld\n", (Z.A[1][1]+Z.A[1][2]+Z.A[1][3])%mod);}int main(){    scanf("%d",&T);    while(T--)    {        scanf("%lld",&n);        init();        work();    }    return 0;}