#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef vector<ll>vi;
typedef pair<ll,ll>pi;
const ll mod=1e9+7;
ll qpow(ll a,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
ll n;
namespace seq
{
    const int N=1e4+10;
    ll res[N],base[N],c[N],md[N];
    vi v;
    void mul(ll *a,ll *b,long long k)
    {
        for(int i=0;i<k+k;i++) c[i]=0;
        for(ll i=0;i<k;i++)
            if(a[i])
            for(ll j=0;j<k;j++)
            c[i+j]=(c[i+j]+a[i]*b[j])%mod;
        for(ll i=k+k-1;i>=k;i--)
            if(c[i])
            for(int j=0;j<v.size();j++)
            c[i-k+v[j]]=(c[i-k+v[j]]-c[i]*md[v[j]])%mod;
        for(int i=0;i<k;i++) a[i]=c[i];
    }
    ll solve(ll n,vi a,vi b)
    {
        // a系数 b初值 b[n+1]=a[0]*b[n]+...
        //for(int i=0;i<a.size();i++)
        //    printf(i==a.size()-1?"%lld\n":"%lld ",a[i]);a是最短递推式
        ll ans=0,len=0;
        ll k=a.size();
        for(int i=0;i<k;i++) md[k-1-i]=-a[i];md[k]=1;
        v.clear();
        for(int i=0;i<k;i++)
            if(md[i]!=0) v.push_back(i);
        for(int i=0;i<k;i++) res[i]=base[i]=0;
        res[0]=1;
        while((1ll<<len)<=n) len++;
        for(ll p=len;p>=0;p--)
        {
            mul(res,res,k);
            if((n>>p)&1)
            {
                for(ll i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
                for(int j=0;j<v.size();j++) res[v[j]]=(res[v[j]]-res[k]*md[v[j]])%mod;
            }
        }
        for(int i=0;i<k;i++) ans=(ans+res[i]*b[i])%mod;
        return (ans%mod+mod)%mod;
    }
    vi BM(vi s)
    {
        vi ans(1,1),res(1,1);
        ll l=0,m=1,b=0;
        for(int n=0;n<s.size();n++)
        {
            ll d=0;
            for(int i=0;i<=l;i++) d=(d+(ll)ans[i]*s[n-i])%mod;
            if(d==0) m++;
            else if(2*l<=n)
            {
                vi t=ans;
                ll c=mod-d*qpow(b,mod-2)%mod;
                while(ans.size()<res.size()+m) ans.pb(0);
                for(int i=0;i<res.size();i++)
                ans[i+m]=(ans[i+m]+c*res[i])%mod;
                l=n+1-l;res=t;b=d;m=1;
            }
            else
            {
                ll c=mod-d*qpow(b,mod-2)%mod;
                while(ans.size()<res.size()+m) res.pb(0);
                for(int i=0;i<res.size();i++)
                    ans[i+m]=(ans[i+m]+c*res[i])%mod;
                m++;
            }
        }
        return ans;
    }
    ll getans(vi a,ll n)
    {
        vi c=BM(a);
        c.erase(c.begin());
        for(int i=0;i<c.size();i++) c[i]=(mod-c[i])%mod;
        return solve(n,c,vi(a.begin(),a.begin()+c.size()));
    }
};
int main()
{
    /*
    vi v;
    for(int i=1;i<=50;i++)
    {
        long long ans=0;int n=i;
        for(int s1=0;s1<=n;s1++)
        for(int s2=s1+1;s1+s2<=n;s2++)
        {
            for(int n1=0;n1+s1+s2<=n;n1++)
            for(int n2=n1+1;n1+n2+s1+s2<=n;n2++)
            {
                for(int u1=0;u1+n1+n2+s1+s2<=n;u1++)
                for(int u2=u1+1;u1+u2+n1+n2+s1+s2<=n;u2++)
                {
                    for(int k1=0;k1+u1+u2+n1+n2+s1+s2<=n;k1++)
                    for(int k2=k1+1;k1+k2+u1+u2+n1+n2+s1+s2<=n;k2++)
                    {
                        for(int e1=0;e1+k1+k2+u1+u2+n1+n2+s1+s2<=n;e1++)
                        for(int e2=e1+1;e1+e2+k1+k2+u1+u2+n1+n2+s1+s2<=n;e2++)
                        {
                            ans+=(long long)(s2-s1)*(n2-n1)%mod*(u2-u1)%mod*(k2-k1)%mod*(e2-e1)%mod;
                            ans%=mod;
                        }
                    }
                }
            }
        }
        printf("%lld,",ans);
        v.pb(ans);
    }
    */
    int t;scanf("%d",&t);
    while(t--)
    {
        int n;scanf("%d",&n);
        printf("%lld\n",seq::getans(vi{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,697944950},n-1));
    }
}
                                     //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,697944950,247718575,502478077,491383141,292066399,231133366,338549256



Measured memory_bytes: 3700