#pragma GCC optmize (2)
#pragma GCC optmize ("unroll-loops")
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 262149
#define ll long long
#define reg register
#define pi 3.141592653589793
#define p 1000000007
using namespace std;

inline int add(const int& x,const int& y){ return x+y>=p?x+y-p:x+y; }
inline int dec(const int& x,const int& y){ return x<y?x-y+p:x-y; }
const int inv2 = (p+1)>>1;

inline void read(int &x){
    x = 0;
    char c = getchar();
    while(c<'0'||c>'9') c = getchar();
    while(c>='0'&&c<='9'){
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
}

inline int power(int a,int t){
    int res = 1;
    while(t){
        if(t&1) res = (ll)res*a%p;
        a = (ll)a*a%p;
        t >>= 1; 
    }
    return res;
}

struct complex{
    double r,i;
    inline complex(double r=0,double i=0):r(r),i(i){}

    inline complex operator * (const complex& x) const{ return complex(r*x.r-i*x.i,i*x.r+r*x.i); }
    inline complex operator ~ () const{ return complex(r,-i); }
    inline complex operator + (const complex& x) const{ return complex(r+x.r,i+x.i); }
    inline complex operator - (const complex& x) const{ return complex(r-x.r,i-x.i); }
    inline complex operator / (const int& x) const{ return complex(r/x,i/x); }
};

int rev[N],inv[N],fac[N],ifac[N];
complex rt[N];
int siz;

void init(int n){
    int lim = 1;
    while(lim<=n) lim <<= 1,++siz;
    for(reg int i=1;i!=lim;++i) rev[i] = (rev[i>>1]>>1)|((i&1)<<(siz-1));
    inv[1] = 1;
    rt[lim>>1] = complex(1,0);
    for(reg int i=1;i!=(lim>>1);++i) rt[i+(lim>>1)] = complex(cos(pi*i/lim*2),sin(pi*i/lim*2));
    for(reg int i=(lim>>1)-1;i;--i) rt[i] = rt[i<<1];
    for(reg int i=2;i<=lim;++i) inv[i] = (ll)(p-p/i)*inv[p%i]%p;
    fac[0] = fac[1] = 1;
    for(int i=2;i<=n;++i) fac[i] = (ll)fac[i-1]*i%p;
}

inline int getlen(int n){
    return 1<<(32-__builtin_clz(n));    
}

inline void dft(complex *f,int lim){
    static complex a[N],x;
    int shift = siz-__builtin_ctz(lim);
    for(reg int i=0;i!=lim;++i) a[rev[i]>>shift] = f[i];
    for(reg int mid=1;mid!=lim;mid<<=1)
    for(reg int j=0;j!=lim;j+=(mid<<1))
    for(reg int k=0;k!=mid;++k){
        x = a[j|k|mid]*rt[mid|k];
        a[j|k|mid] = a[j|k]-x;
        a[j|k] = a[j|k]+x;
    }
    for(reg int i=0;i!=lim;++i) f[i] = a[i];
    
}

inline void idft(complex *f,int lim){
    reverse(f+1,f+lim);
    dft(f,lim);
    for(reg int i=0;i!=lim;++i) f[i] = f[i]/lim;
}

int inv_flg;
complex inv_tp[N];

void multiply(const int *A,const int *B,int n,int m,int *R,int len,bool sq=false){
    static complex f[N],g[N],h[N],q[N];
    register complex t,f0,f1,g0,g1;
    register ll x,y,z;
    int lim = getlen(n+m);
     for(reg int i=0;i!=lim;++i){
        f[i] = complex(A[i]>>15,A[i]&32767);
        g[i] = complex(B[i]>>15,B[i]&32767);
    } 
    dft(f,lim);
    if(sq) for(int i=0;i!=lim;++i) g[i] = f[i];
    else if(inv_flg==1) for(int i=0;i!=lim;++i) g[i] = inv_tp[i];
    else dft(g,lim);
    if(inv_flg==2) for(int i=0;i!=lim;++i) inv_tp[i] = g[i];
    for(reg int i=0;i!=lim;++i){
        t = ~f[i?lim-i:0];
        f0 = (f[i]-t)*complex(0,-0.5),f1 = (f[i]+t)*0.5;
        t = ~g[i?lim-i:0];
        g0 = (g[i]-t)*complex(0,-0.5),g1 = (g[i]+t)*0.5;
        h[i] = f1*g1;
        q[i] = f1*g0 + f0*g1 + f0*g0*complex(0,1);
    }
    idft(h,lim),idft(q,lim);
    for(reg int i=0;i<=len;++i){
        x = (ll)(h[i].r+0.5)%p<<30;
        y = (ll)(q[i].r+0.5)<<15;
        z = q[i].i+0.5;
        R[i] = (x+y+z)%p;
    }
}

inline void inverse(const int *f,int n,int *R){
    static int g[N],h[N],q[N];
    memset(g,0,getlen(n<<1)<<2);
    int lim = 1,top = 0;
    int s[30];
    while(n){
        s[++top] = n;
        n >>= 1;
    }
    g[0] = 1;
    while(top--){
        n = s[top+1];
        while(lim<=(n<<1)) lim <<= 1;
        memcpy(h,f,(n+1)<<2);
        memset(h+n+1,0,(lim-n)<<2);
        inv_flg = 2;
        multiply(h,g,n,n,h,n);
        inv_flg = 1;
        multiply(h,g,n,n,h,n);
        inv_flg = 0;
        for(reg int i=0;i<=n;++i) g[i] = dec(add(g[i],g[i]),h[i]);
    }
    
    memcpy(R,g,(n+1)<<2);
}

inline void log(int *f,int n){
    static int g[N];
    inverse(f,n,g);
    for(reg int i=0;i!=n;++i) f[i] = (ll)f[i+1]*(i+1)%p;
    f[n] = 0;
    int lim = getlen(n<<1);
    memset(g+n+1,0,(lim-n)<<2);
    multiply(f,g,n,n,f,n);
    for(reg int i=n;i;--i) f[i] = (ll)f[i-1]*inv[i]%p;
    f[0] = 0;
}

void exp(const int *f,int n,int *R){
    static int g[N],h[N];   
    memset(g,0,getlen(n<<1)<<2);
    int lim = 1,top = 0;
    int s[30];
    while(n){
        s[++top] = n;
        n >>= 1;    
    }
    g[0] = 1;
    while(top--){
        n = s[top+1];
        while(lim<=(n<<1)) lim <<= 1;
        memcpy(h,g,lim<<2);
        log(g,n);
        for(reg int i=0;i<=n;++i) g[i] = dec(f[i],g[i]);
        g[0]++;
        multiply(g,h,n,n,g,n);
    }
    memcpy(R,g,(n+1)<<2);
}

inline void print(const int *f,int n){
    for(int i=0;i<=n;++i) printf("%d ",f[i]);
    putchar('\n');
}

void solve_DE(int n,int *D,int *E){
    static int exD[N],fD[N],dfD[N],exE[N],st[30];
    int lim = 1,top = 0;
    while(n){
        st[++top] = n;
        n >>= 1;
    }
    while(top--){
        n = st[top+1];
        while(lim<=(n<<1)) lim <<= 1;
        exp(D,n,exD);
        multiply(exD,exD,n,n,E,n,true);
        for(int i=0;i<=n;++i){
            dfD[i] = dec(add(E[i],E[i]),exD[i]);
            E[i] = dec(E[i],add(exD[i],D[i]));
        }
        E[1]++; dfD[0]--;
        exp(E,n,exE);
        for(int i=0;i<=n;++i) fD[i] = dec(add(E[i],D[i]),exE[i]);
        fD[0]++,fD[1]--;
        for(int i=0;i<=n;++i) exE[i] = p-exE[i];
        exE[0]++;
        multiply(exE,dfD,n,n,dfD,n);
        dfD[0]++;
        inverse(dfD,n,dfD);
        multiply(fD,dfD,n,n,fD,n);
        for(int i=0;i<=n;++i) D[i] = dec(D[i],fD[i]);
    }
    
    exp(D,n,exD);
    multiply(exD,exD,n,n,E,n);
    for(int i=0;i<=n;++i) E[i] = dec(E[i],add(exD[i],D[i]));
    E[1]++; 
    
}

void solve_BC(int n,int *B,int *C){
    static int B2[N],exB2[N],exB[N],exC[N],fB[N],dfB[N],st[30];
    int lim = 1,top = 0;
    while(n){
        st[++top] = n;
        n >>= 1;
    }
    while(top--){
        n = st[top+1];
        while(lim<=(n<<1)) lim <<= 1;
        for(int i=0;i<=n;++i) B2[i] = (ll)B[i]*inv2%p;
        exp(B2,n,exB2);
        multiply(exB2,exB2,n,n,exB,n,true);
        for(int i=0;i<=n;++i) C[i] = (2ll*(p+exB[i]-exB2[i])-B[i])%p;
        C[1] += 2;
        exp(C,n,exC);
        for(int i=0;i<=n;++i) fB[i] = dec(add(B[i],C[i]),exC[i]);
        fB[0]++; fB[1] -= 2;
        for(int i=0;i<=n;++i) dfB[i] = dec(add(exB[i],exB[i]),exB2[i]);
        for(int i=0;i<=n;++i) exC[i] = p-exC[i];
        dfB[0]--; exC[0]++;
        multiply(dfB,exC,n,n,dfB,n);
        dfB[0]++;
        inverse(dfB,n,dfB);
        multiply(fB,dfB,n,n,fB,n);
        for(int i=0;i<=n;++i) B[i] = dec(B[i],fB[i]);
    }
    
    for(int i=0;i<=n;++i) B2[i] = (ll)B[i]*inv2%p;
    exp(B2,n,exB2);
    multiply(exB2,exB2,n,n,exB,n);
    for(int i=0;i<=n;++i) C[i] = (2ll*(p+exB[i]-exB2[i])-B[i])%p;
    C[1] += 2;
    
}

int n = 60000,k,T;
int A[N],B[N],C[N],D[N],E[N];

int main(){
    init(n<<2);
    solve_DE(n,D,E);
    solve_BC(n,B,C);
    for(int i=1;i<=n;++i) A[i] = dec(add(B[i],C[i]),add(D[i],E[i]));
    A[1]--;
    for(int i=1;i<=n;++i) A[i] = ((ll)A[i]*fac[i]%p+p)%p;
    //A[33303] = 3743073;
    //for(int i=0;i<=n;++i) printf("%d,",A[i]);
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        printf("%d\n",A[n]);
    }
    return 0;   
}