#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

using namespace std;

const int N=,Mod=;

struct node{

    int sx,sy;

    int s[][];

};

node mult(node a,node b)

{

    node c;

    c.sx=a.sx;c.sy=b.sy;

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

    for(int i=;i<=a.sx;i++)

        for(int j=;j<=b.sy;j++)

            for(int k=;k<=a.sx;k++)

            {

                c.s[i][j]+=(a.s[i][k]*b.s[k][j])%Mod;

                c.s[i][j]%=Mod;

            }

    return c;

}

void solve(int x)

{

    node a;

    a.sx=a.sy=;

    a.s[][]=;a.s[][]=;a.s[][]=;

    a.s[][]=a.s[][]=a.s[][]=;

    a.s[][]=;a.s[][]=;a.s[][]=;

    node b;

    b.sx=b.sy=;

    memset(b.s,,sizeof(b.s));

    for(int i=;i<=;i++) b.s[i][i]=;

    while(x)

    {

        if(x&) b=mult(b,a);

        a=mult(a,a);

        x>>=;

    }

    node c;

    c.sx=;c.sy=;

    c.s[][]=;

    c.s[][]=c.s[][]=;

    c=mult(b,c);

    printf("%d\n",c.s[][]);

    return ;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int x;

        scanf("%d",&x);

        solve(x);

    }

    return ;

}