#include <bits/stdc++.h>

using namespace std;

const long long mod=1e9+;

const long long inf=1e18;

int T;

long long n;

struct Matrix

{

    long long A[][];

    int R, C;

    Matrix operator*(Matrix b);

};

Matrix X, Y, Z;

Matrix Matrix::operator*(Matrix b)

{

    Matrix c;

    memset(c.A, , sizeof(c.A));

    int i, j, k;

    for (i = ; i <= R; i++)

        for (j = ; j <= C; j++)

            for (k = ; 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 - ;

    memset(X.A,,sizeof X.A);

    memset(Y.A,,sizeof Y.A);

    memset(Z.A,,sizeof Z.A);

    Z.R = ; Z.C = ;

    Z.A[][]=; Z.A[][]=; Z.A[][]=;

    for(int i=;i<=;i++) Y.A[i][i]=; Y.R = ; Y.C = ;

    X.A[][]=; X.A[][]=; X.A[][]=;

    X.A[][]=; X.A[][]=; X.A[][]=;

    X.A[][]=; X.A[][]=; X.A[][]=;

    X.R = ; X.C = ;

}

void work()

{

    while (n)

    {

        if (n %  == ) Y = Y*X;

        n = n >> ;

        X = X*X;

    }

    Z = Z*Y;

    printf("%lld\n", (Z.A[][]+Z.A[][]+Z.A[][])%mod);

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        scanf("%lld",&n);

        init();

        work();

    }

    return ;

}