#include<set>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cassert>

#include<cstring>

#include<algorithm>

using namespace std;

#define rep(i,a,n) for (ll i=a;i<n;i++)

#define per(i,a,n) for (ll i=n-1;i>=a;i--)

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define SZ(x) ((ll)(x).size())

#define all(x) (x).begin(),(x).end()

typedef long long ll;

typedef vector<ll> VI;

typedef pair<ll, ll> PII;

const ll mod=;

ll powmod(ll a, ll b)

{

    ll res=;

    a%=mod;

    assert(b>=);

    for(;b;b>>=)

    {

        if(b&)

            res=res*a%mod;

        a=a*a%mod;

    }

    return res;

}

ll _,n;

namespace linear_seq

 {

    const ll N=;

    ll res[N],base[N],_c[N],_md[N];

    vector<ll>Md;

    void mul(ll*a,ll*b,ll k)

    {

        rep(i,,k+k) _c[i]=;

        rep(i,,k) if(a[i]) rep(j,,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;

        for(ll i=k+k-;i>=k;i--) if(_c[i])

        rep(j,,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;

        rep(i,,k) a[i]=_c[i];

    }

    ll solve(ll n, VI a, VI b)

    {

        ll ans=,pnt=;

        ll k=SZ(a);

        assert(SZ(a)==SZ(b));

        rep(i,,k) _md[k--i]=-a[i]; _md[k]=;

        Md.clear();

        rep(i,,k) if(_md[i]!=) Md.push_back(i);

        rep(i,,k) res[i]=base[i]=;

        res[]=;

        while((1ll<<pnt)<=n) pnt++;

        for(ll p=pnt;p>=;p--)

        {

            mul(res,res,k);

            if((n>>p)&)

            {

                for(ll i=k-;i>=;i--) res[i+]=res[i]; res[]=;

                rep(j,,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;

            }

        }

        rep(i,,k) ans=(ans+res[i]*b[i])%mod;

        if(ans<) ans+=mod;

        return ans;

    }

    VI BM(VI s)

    {

        VI C(,),B(,);

        ll L=,m=,b=;

        rep(n,,SZ(s))

        {

            ll d=;

            rep(i,,L+) d=(d+(ll)C[i]*s[n-i])%mod;

            if(d==) ++m;

            else if(*L<=n)

            {

                VI T=C;

                ll c=mod-d*powmod(b,mod-)%mod;

                while(SZ(C)<SZ(B)+m) C.pb();

                rep(i,,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;

                L=n+-L; B=T; b=d; m=;

            }

            else

            {

                ll c=mod-d*powmod(b,mod-)%mod;

                while(SZ(C)<SZ(B)+m) C.pb();

                rep(i,,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;

                ++m;

            }

        }

        return C;

    }

    ll gao(VI a,ll n)

    {

        VI c=BM(a);

        c.erase(c.begin());

        rep(i,,SZ(c)) c[i]=(mod-c[i])%mod;

        return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));

    }

};

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%lld", &n);

        VI vec;

        vec.push_back();

        vec.push_back();

        vec.push_back();

        vec.push_back();

        vec.push_back();

        vec.push_back();

        vec.push_back();

        printf("%lld\n", linear_seq::gao(vec, n - )%mod);

    }

}