#define DIN freopen("input.txt","r",stdin);
#define DOUT freopen("output.txt","w",stdout);
#include <bits/stdc++.h>
#include <cstdio>
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define REP_(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<LL,LL> P;
int read()
{
    int x=0,flag=1; char c=getchar();
    while((c>'9' || c<'0') && c!='-') c=getchar();
    if(c=='-') flag=0,c=getchar();
    while(c<='9' && c>='0') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return flag?x:-x;
}

const int maxn=40005;
const LL M=1e9+7;
struct linear_sequence
{
    LL res[maxn],base[maxn],_c[maxn],_md[maxn];
    VI Md;

    LL ksm(LL x,LL n)
    {
        LL ret=1;
        while(n)
        {
            if(n&1) ret=ret*x%M;
            x=x*x%M;
            n>>=1;
        }
        return ret;
    }
    void multi(LL *a,LL *b,int k)
    {
        REP(i,0,(k<<1)-1) _c[i]=0;
        REP(i,0,k-1) if(a[i]) REP(j,0,k-1)
            _c[i+j]=(_c[i+j]+a[i]*b[j])%M;
        REP_(i,k+k-1,k) if(_c[i]) REP(j,0,Md.size()-1)
            _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%M;
        REP(i,0,k-1) a[i]=_c[i];
    }
    int solve(LL n,VI a,VI b)
    {
        LL ans=0,pnt=0;
        int k=a.size();
        //assert(a.size()==b.size());
        REP(i,0,k-1) _md[k-1-i]=-a[i];
        _md[k]=1;
        Md.clear();
        REP(i,0,k-1) if(_md[i]) Md.pb(i);
        REP(i,0,k-1) res[i]=base[i]=0;
        res[0]=1;
        while((1ll<<pnt)<=n) pnt++;
        REP_(p,pnt,0)
        {
            multi(res,res,k);
            if((n>>p)&1)
            {
                REP_(i,k-1,0) res[i+1]=res[i];
                res[0]=0;
                REP(j,0,Md.size()-1) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%M;
            }
        }
        REP(i,0,k-1) ans=(ans+res[i]*b[i])%M;
        return (ans+M)%M;
    }
    VI BM(VI s)
    {
        VI C(1,1),B(1,1);
        int L=0,m=1,b=1;
        REP(n,0,s.size()-1)
        {
            LL d=0;
            REP(i,0,L) d=(d+(LL)C[i]*s[n-i])%M;
            if(!d) ++m;
            else if((L<<1)<=n)
            {
                VI T=C;
                LL c=M-d*ksm(b,M-2)%M;
                while(C.size()<B.size()+m) C.pb(0);
                REP(i,0,B.size()-1) C[i+m]=(C[i+m]+c*B[i])%M;
                L=n+1-L,B=T,b=d,m=1;
            }
            else
            {
                LL c=M-d*ksm(b,M-2)%M;
                while(C.size()<B.size()+m) C.pb(0);
                REP(i,0,B.size()-1) C[i+m]=(C[i+m]+c*B[i])%M;
                ++m;
            }
        }
        return C;
    }
    int get(VI a,LL n)
    {
        VI c=BM(a);
        c.erase(c.begin());
        REP(i,0,c.size()-1) c[i]=(M-c[i])%M;
        //for(int i:c) printf("%d ",i);
        //puts("");
        return solve(n,c,VI(a.begin(),a.begin()+c.size()));
    }
}ls;

int cal(int n)
{
    LL ret=0;
    REP(s1,0,n-4) REP(s2,s1+1,n-4) if(s1+s2<=n-4)
        REP(n1,0,n-4) REP(n2,n1+1,n-4) if(s1+s2+n1+n2<=n-3)
            REP(u1,0,n-4) REP(u2,u1+1,n-4) if(s1+s2+n1+n2+u1+u2<=n-2)
                REP(k1,0,n-4) REP(k2,k1+1,n-4) if(s1+s2+n1+n2+u1+u2+k1+k2<=n-1)
                    REP(e1,0,n-4) REP(e2,e1+1,n-4)
                    {
                        int tot=s1+s2+n1+n2+u1+u2+k1+k2+e1+e2;
                        if(tot>n) continue;
                        ret+=1ll*(s2-s1)*(n2-n1)*(u2-u1)*(k2-k1)*(e2-e1);
                    }
    return ret%M;
}

int f[]={
0,
0,
0,
0,
1,
11,
71,
341,
1346,
4598,
14038,
39138,
101193,
245443,
563447,
1232837,
2585672,
5222552,
10198232,
19316488,
35588718,
63933498,
112225058,
192839398,
324900532,
537499132,
874246012,
399637805,
207858088,
434820093,
274485959,
780358,
996765147,
793168065,
118878018,
966647141,
677996797,
52230779,
485540255,
147468710,
203524158,
94513877,
885277100,
};

int main()
{
    VI x;
    /*
    REP(i,1,50)
    {
        cout<<cal(i)<<','<<endl;
        //x.pb(cal(i));
    }
    */
    for(int i:f) x.pb(i);
    int T=read();
    while(T--)
    {
        int n=read();
        printf("%d\n",ls.get(x,n-1));
    }

    return 0;
}


Measured memory_bytes: 3736