#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007LL

ll mod_pow(ll x,ll n){
  ll res=1;
  while(n>0LL){
    if(n&1LL)res=res*x%mod;
    x=x*x%mod;
    n>>=1LL;
  }
  return res;
}
/*
vector<ll> newton_interpol(ll D, const vector<ll>& X, const vector<ll>& Y){
  vector<ll> res(D, 0), C(D);
  vector<vector<ll>> dp(D + 1, vector<ll>(D + 1, 0));
 
  // construct C array
  for(ll i = 0; i < D; i++) {
    ll sum = 0, crt = 1;
    for(ll j = 0; j < i; j++) {
      sum += crt * C[j] % mod;
      sum %= mod;
      crt *= (X[i] - X[j] + mod);
      crt %= mod;
    }
    C[i] = (Y[i] - sum + mod) % mod;
    C[i] *= mod_pow(crt, mod - 2);
    C[i] %= mod;
  }
 
  // calc polynomial (dp)
  dp[0][0] = 1;
  for(ll i = 0; i < D; i++) {
    for(ll j = 0; j <= i; j++) {
      res[j] += C[i] * dp[i][j] % mod;
      res[j] %= mod;
    }
    if(i == D - 1) break;
    for(ll j = 0; j <= i; j++) {
      (dp[i + 1][j] += dp[i][j] * (D - X[i] + mod)) %= mod;
      (dp[i + 1][j + 1] += dp[i][j]) %= mod;
    }
  }
 
  return res;
}*/

vector<ll> lagrange_interpolation(vector<ll> x, vector<ll> y) {
    const ll n = x.size() - 1;
    rep(i, n+1) {
        ll t = 1;
        rep(j, n+1) if(i != j) (t *= (x[i]-x[j]+mod))%=mod;
        y[i] *= mod_pow(t, mod-2);
        y[i] %= mod;
    }
    ll cur = 0, nxt = 1;
    vector<vector<ll>> dp(2, vector<ll>(n+2));
    dp[0][0] = (mod - x[0])%mod, dp[0][1] = 1;
    repl(i, 1, n+1) {
        rep(j, n+2) {
            dp[nxt][j] = (dp[cur][j] * x[i] % mod) * (mod - 1) % mod;
            if(j >= 1) (dp[nxt][j] += dp[cur][j-1])%=mod;
        }
        swap(nxt, cur);
    }
    vector<ll> xinv(n+1);
    rep(i, n+1) xinv[i] = mod_pow(x[i], mod-2);
    vector<ll> ret(n+1);
    rep(i, n+1) {
        if(y[i]==0) continue;
        if(x[i] == 0) {
            rep(j, n+1) (ret[j] += dp[cur][j+1] * y[i] % mod) %= mod;
        } else {
            ret[0] = (ret[0] + mod - ((dp[cur][0] * xinv[i] % mod) * y[i] % mod))%mod;
            ll pre = (dp[cur][0] * xinv[i] % mod) * (mod - 1) % mod;
            repl(j, 1, n+1) {
                ret[j] = (ret[j] + mod - (((dp[cur][j] - pre) * xinv[i] % mod) * y[i] % mod)) % mod;
                pre = ((dp[cur][j] - pre) * xinv[i] % mod) * (mod - 1) % mod;
            }
        }
    }
    return ret;
}

ll dp[6][111];

ll dfs(ll i,ll s) {
  if(i==5) return 1;
  if(dp[i][s]!=-1)return dp[i][s];
  ll res=0;
  rep(c1,s+1){
    repl(c2,c1+1,s-c1+1){
      res+=dfs(i+1,s-c1-c2)*(c2-c1)%mod;
      res%=mod;
    }
  }
  return dp[i][s]=res;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  rep(i,6)rep(j,111)dp[i][j]=-1;

  const ll m=100;
  vector<ll> X[2],Y[2];
  for(ll x=5;x<=5+m-1;x++){
    ll ans=dfs(0,x);

    X[x%2].push_back(x);
    Y[x%2].push_back(ans);
  }
  vector<ll> A[2];
  A[0]=lagrange_interpolation(X[0],Y[0]);
  A[1]=lagrange_interpolation(X[1],Y[1]);

  int T;
  cin>>T;
  while(T--){
    ll N;
    cin>>N;
    ll ans=0;
    rep(i,A[N%2].size()){
      ans+=A[N%2][i]*mod_pow(N,i)%mod;
      ans%=mod;
    }
    cout<<ans<<"\n";
  }

  return 0;
}


Measured memory_bytes: 3676