shop

#include <fstream>
#define N 10001
#define M 1000000007
using namespace std;
int F[N],P[5001];

void factoriale()
{
    int m, p, pro;
    F[0]=1,P[0]=1;
    /// Aici se calculeaza factorialele pana la 5000 si produsele partiale de factoriale
    for(int i=1;i<=5000;++i)
        F[i]=(1LL*F[i-1]*i)%M,P[i]=(1LL*P[i-1]*F[i])%M;
    /// Aici se calculeaza n!, unde n=k*(k+1)/2, pentru k>=100;
    /// la factorialul calculat anterior se adauga doi factori deodata
    /// produsul (j+2)*(j+3) difera de j*(j+1) prin 4*j+6
    p=F[5000];
    int j=5001;
    pro=j*(j+1);
    for(int i=100;i<=5000;++i)
    {
        m=i*(i+1)/2;
        while(j<m)
            p=(1LL*p*pro)%M,pro=(pro+4*j+6)%M,j+=2;
        if(j==m+1)
            F[4901+i]=p;
        else
            F[4901+i]=(1LL*p*m)%M;
    }
}

int pw(int b,int e)
{
    if(e==0)
        return 1;
    if(e%2==0)
    {
        int x=pw(b,e/2);
        return (1LL*x*x)%M;
    }
    else
        return (1LL*b*pw(b,e-1))%M;
}

int main()
{
    ifstream f("shop.in");
    factoriale();
    int t;
    f>>t;
    int k,sol;
    ofstream g("shop.out");
    while(t--)
    {
        f>>k;
        int n=k*(k+1)/2,d;
        if(n<=5000)
            d=F[n];
        else
            d=F[4901+k];
        sol=(1LL*d*pw(P[k],M-2))%M;
        g<<sol<<'\n';
    }
    f.close(),g.close();
    return 0;
}