#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;


inline ll mpow(ll a, ll b, ll p = -1){
  ll ret = 1, num = a;
  while(b>0){
    if(b&1) ret = (ret*num)%p;
    num = (num*num)%p;
    b /= 2;
  }
  return ret;
}

#include <random>
// modpow(x,2,mod) == aとなるxを返す
// 存在しないなら-1
// mod は素数
ll modsqrt(ll a, ll mod) {
  a %= mod;
	if(a == 0) return 0LL;
	if(mod == 2) return 1LL;
	if(mpow(a, (mod - 1) / 2, mod) != 1) return -1LL;
	if(mod % 4 == 3) return mpow(a, mod / 4 + 1, mod);
	ll q = mod - 1, m = 0;
	while(q % 2 == 0) q >>= 1, m++;
	mt19937 mt;
	ll z;
	do {
		z = mt() % mod;
	} while(mpow(z, (mod - 1) / 2, mod) != mod - 1);
	ll c = mpow(z, q, mod);
	ll t = mpow(a, q, mod);
	ll r = mpow(a, (q + 1) >> 1, mod);
	for(; m > 1; --m) {
	  ll tmp = mpow(t, 1LL << (m - 2), mod);
		if(tmp != 1) r = r * c % mod, t = t * (c * c % mod) % mod;
		c = c * c % mod;
	}
	return r;
}

template<ll P, ll proot>
struct NTT{
  ll g;
	vector<ll> primes;
  NTT(){};
  ll get_mod(){return P;}
  void ntt(vector<ll>&f, bool inv){
    int n, N = f.size();
    g = mpow(proot, P/N, P);
  	vector<ll> angles(N);angles[0] = 1;
    for(int i=1;i<N;i++) angles[i] = (angles[i-1] * g)%P;
  	for(n=0;;n++) if(N == (1<<n)) break;
  	for (int m=0;m<N;m++) {
  		int m2 = 0;
  		for(int i=0;i<n;i++) if(m&(1<<i)) m2 |= (1<<(n-1-i));
  		if(m < m2) swap(f[m], f[m2]);
  	}

    for(int i=0;i<N;i++) f[i] %= P;
    vector<ll> power(N/2);
    power[0] = 1;
  	for(int t=1;t<N;t*=2) {
  		ll w = angles[N/(2*t)];
  		if(inv) w = angles[N - N/(2*t)];
      for(int i=1;i<t;i++) power[i] = (power[i-1] * w)%P;
  		for(int i=0;i<N;i+=2*t){
  			for (int j=0;j<t;j++){
          ll x = f[i+j], y = f[i+t+j];
  				f[i+j] = (x + y * power[j])%P;
  				f[i+t+j] = x  - (y * power[j])%P;
          if(f[i+t+j]<0) f[i+t+j] += P;
  			}
  		}
  	}
  	if(inv) {
  		ll inv = mpow(N, P-2, P);
  		for(int i=0;i<N;i++) f[i] = (f[i]*inv)%P;
  	}
  }
  vector<ll> conv(vector<ll> A, vector<ll> B){
    assert(A.size()==B.size());
    ll N = A.size();
    vector<ll> C(N);
    ntt(A, 0);
    ntt(B, 0);
    for(int i=0;i<N;i++) C[i] = (A[i] * B[i])%P;
    ntt(C, 1);
    return C;
  }
};

vector<ll> int32mod_conv(vector<ll> a, vector<ll> b, ll P){
  if(P==998244353) return NTT<998244353, 3>().conv(a, b);
  NTT<167772161, 3> ntt1;
  NTT<469762049, 3> ntt2;
  NTT<1224736769, 3> ntt3;
  vector<ll> A = ntt1.conv(a, b);
  vector<ll> B = ntt2.conv(a, b);
  vector<ll> C = ntt3.conv(a, b);
  ll N = A.size();
  vector<ll> ret(N);
  ll x = ntt1.get_mod();
  ll y = ntt2.get_mod();
  ll z = ntt3.get_mod();
  ll ix = mpow(x, y-2, y);
  ll ixy = mpow((x*y)%z, z-2, z);
  for(int i=0;i<N;i++){
    ll v = ((B[i] - A[i])*ix)%y;
    if(v<0) v += y;
    ll xxv = A[i]+x*v;
    v = ((C[i] - (xxv%z))*ixy)%z;
    if(v<0) v += z;
    ret[i] = ((xxv%P) + ((x*y)%P)*v)%P;
  }
  return ret;
}


template<ll P>
struct FPS: vector<ll>{
  using vector<ll>::vector;

  static vector<ll> itable;//integral用の逆元テーブル

  FPS(vll a){
    ll N = 1, n = a.size();
    while(N < n) N *= 2;
    this->resize(n);
    for(int i=0;i<n;i++) (*this)[i] = a[i];
  }

  FPS operator + (const FPS& r){return FPS(*this) += r;}
  FPS operator - (const FPS& r){return FPS(*this) -= r;}
  FPS operator * (const FPS& r){return FPS(*this) *= r;}
  FPS operator / (const FPS& r){return FPS(*this) /= r;}
  FPS operator + (const ll& r){return FPS(*this) += r;}
  FPS operator - (const ll& r){return FPS(*this) -= r;}
  FPS operator * (const ll& r){return FPS(*this) *= r;}
  FPS operator / (const ll& r){return FPS(*this) /= r;}

  //多項式との演算
  FPS operator += (const FPS& r){
    if(r.size() > this->size()) this->resize(r.size());
    for(int i=0;i<r.size();i++) {
      (*this)[i] += r[i];
      if((*this)[i]>P) (*this)[i] -= P;
    }
    return *this;
  }

  FPS operator -= (const FPS& r){
    if(r.size() > this->size()) this->resize(r.size());
    for(int i=0;i<r.size();i++) {
      (*this)[i] -= r[i];
      if((*this)[i]<0) (*this)[i] += P;
    }
    return *this;
  }
  FPS operator *= (FPS r){
    ll n = max(this->size(), r.size()) * 2, N = 1;
    while(N < n) N*=2;
    this->resize(N);
    r.resize(N);
    return (*this) = (int32mod_conv(*this, r, P));
  }
  FPS operator /= (FPS r){ return (*this) *= r.inv();}

  //定数との演算
  FPS operator += (const ll& r){
    if(this->empty()) this->resize(1);
    (*this)[0] += r;
    if((*this)[0]>P) (*this)[0] -= P;
    return *this;
  }
  FPS operator -= (const ll& r){
    if(this->empty()) this->resize(1);
    (*this)[0] -= r;
    if((*this)[0]<0) (*this)[0] += P;
    return *this;
  }
  FPS operator *= (const ll& r){
    if(this->empty()) this->resize(1);
    const ll n = this->size();
    for(int i=0;i<n;i++) (*this)[i] = ((*this)[i] * r)%P;
    return *this;
  }

  FPS operator /= (const ll& r){
    if(this->empty()) this->resize(1);
    ll inv = mpow(r, P-2, P);
    const ll n = this->size();
    for(int i=0;i<n;i++) (*this)[i] = ((*this)[i] * inv)%P;
    return *this;
  }
  FPS operator>>(int sz) const {
    if(this->size() <= sz) return {};
    FPS ret = *this;
    ret.erase(ret.begin(), ret.begin() + sz);
    return ret;
  }
  FPS operator<<(int sz) const {
    FPS ret = *this;
    ret.insert(ret.begin(), sz, 0);
    return ret;
  }

  FPS prefix(int deg){
    return FPS(this->begin(), this->begin() + min((int)this->size(), deg));
  }

  FPS inv(int deg=-1){
    assert((*this)[0]!=0);
    const int n = this->size();
    if(deg==-1) deg = n;
    FPS ret({mpow((*this)[0], P-2, P)});
    for(int i=1;i<deg;i<<=1) ret = (ret + ret - ret * ret * prefix(i << 1)).prefix(i << 1);
    return ret.prefix(deg);
  }

  FPS integral(){
    const int n = (int) this->size();
    FPS ret(n+1);
    ret[0] = 0;
    ll inv[n+2];
    inv[0] = inv[1] = 1;
    for(int i=0;i<n;i++) {
      ret[i+1] = ((*this)[i] * inv[i+1])%P;
      inv[i+2] = ((-(P/(i+2))*inv[P%(i+2)])%P+P)%P;
    }
    return ret;
  }

  FPS diff(){
    const int n = (int) this->size();
    FPS ret(max(0, n-1));
    for(int i=1;i<n;i++) ret[i-1] = ((*this)[i] * i)%P;
    return ret;
  }

  FPS log(int deg=-1){
    assert((*this)[0] == 1);
    const int n = (int) this->size();
    if(deg==-1) deg = n;
    return (this->diff() * this->inv(deg)).prefix(deg-1).integral();
  }

  FPS exp(int deg=-1){
    assert((*this)[0]==0);
    const int n = this->size();
    if(deg==-1) deg = n;
    FPS ret(vll{1});
    for(int i=1;i<deg;i<<=1) {
      ret = (ret * (prefix(i << 1) + 1LL - ret.log(i << 1))).prefix(i << 1);
    }
    return ret.prefix(deg);
  }
  void print(FPS a){
    ll n = a.size();
    for(int i=0;i<n-1;i++) printf("%lld ", a[i]);
    printf("%lld\n", a[n-1]);
  }

  //初めて0以外が現れるのが奇数次数or初めに現れる数が平方根でない場合不可能(size0のFPSを返す)
  FPS sqrt(int deg=-1){
    const int n = this->size();
    if(deg==-1) deg = n;
    if((*this)[0]==0){
      for(int i=1;i<n;i++) {
        if((*this)[i]!=0){
          if(i&1){
            std::cout << -1 << '\n';
            exit(0);
          }
          if(deg-i/2<=0) break;
          FPS tmp = (*this >> i).sqrt(deg - i/2);
          if(tmp.size()==0) return {};
          FPS ret = tmp << (i/2);
          if(ret.size()<deg) ret.resize(deg, 0);
          return ret;
        }
      }
      return FPS(deg, 0);
    }
    ll x = modsqrt((*this)[0], P);
    if(x==-1) return {};
    FPS ret({x});
    ll inv2 = mpow(2, P-2, P);
    for(int i=1;i<deg;i<<=1) ret = (ret + this->prefix(i << 1) * ret.inv(i << 1)) * inv2;
    return ret.prefix(deg);
  }

  FPS pow(ll k, int deg=-1) const{
    const int n = (int) this->size();
    if(deg==-1) deg = n;//桁数に注意
    for(ll i=0;i<n;i++) {
      if((*this)[i] != 0) {
        ll rev = mpow((*this)[i], P-2, P);
        FPS C = (*this);
        C *= rev;
        FPS D(deg);
        for(ll j=i;j<n;j++) D[j - i] = C[j];
        D = (D.log(deg) * k).exp(deg) * mpow((*this)[i], k, P);
        FPS E(deg);
        if(i*k>deg) return E;
        auto S = i * k;
        for(ll j=0;j+S<deg&&j<D.size();j++) E[j + S] = D[j];
        return E;
      }
    }
    return *this;
  }

  ll Nth_element(ll N, FPS p, FPS q){
    if(N<=20) return (p/q)[N];
    FPS tmp(q.size(), 0);
    for(int i=0;i<q.size();i++) tmp[i] = (i%2?(P-q[i]):q[i]);
    p *= tmp;
    q *= tmp;
    FPS p2(p.size()/2);
    FPS q2(q.size()/2);
    if(N%2) for(int i=1;i<p.size();i+=2) p2[i/2] = p[i];
    else for(int i=0;i<p.size();i+=2) p2[i/2] = p[i];
    for(int i=0;i<q.size();i+=2) q2[i/2] = q[i];
    return Nth_element(N/2, p2, q2);
  }
};

#define mod 1000000007
typedef FPS<mod> fps;
int main(){
  fps a({1, mod-1}), b({1, 1}), c({0, 0, 0, 0, 0, 1});
  a = a.pow(16, 20) * b.pow(5, 20);
  ll t;scanf("%lld", &t);
  for(int i=0;i<t;i++){
    ll n;scanf("%lld", &n);
    printf("%lld\n", fps().Nth_element(n, c, a));
  }
}


Measured memory_bytes: 3976