/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/

#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

const ll MODBASE = 1000000007LL;
const int MAXN = 210;
const int MAXM = 20;
const int MAXK = 16;
const int MAXQ = 200010;

ll MOD = MODBASE;
ll f[MAXN], rev[MAXN];

ll binPowMod(ll a, ll b) {
    a %= MOD;
    ll res = 1;
    while (b > 0) {
        if (b & 1LL) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1LL;
    }
    return res;
}

ll add(ll a, ll b) {
    return (a + b) % MOD;
}

ll sub(ll a, ll b) {
    return (a - b + MOD) % MOD;
}

ll mul(ll a, ll b) {
    return a * b % MOD;
}

ll C(int n, int k) {
    if (k > n || k < 0) return 0;
    return mul(f[n], mul(rev[n-k], rev[k]));
}

ll calc(int n) {
    ll res = 0;
    for (int i = 0; 2 * i + 5 <= n; i++) res = add(res, mul(C(i+4, 4), C(n+5-2*i, 10)));
    return res;
}

ll inv(ll x) {
    return binPowMod(x, MOD-2);
}

ll LagrangeInterpolation(vector<ll> &y, int n) {
    if (n <= 15) return y[n];
    ll numerator = 1, denominator = 1;
    FOR(i,0,15) {
        numerator = mul(numerator, n - i);
        ll x = (0 - i + MOD) % MOD;
        if (i > 0) denominator = mul(denominator, x);
    }
    ll res = 0;
    FOR(i,0,15) {
        res = add(res, mul(y[i], mul(mul(numerator, inv(n - i)), inv(denominator))));
        ll last = (i - 15 + MOD) % MOD;
        denominator = mul(denominator, inv(last));
        ll newFirst = (i+1) - 0;
        denominator = mul(denominator, newFirst);
    }
    return res;
}

ll solve(int n) {
    if (n < 5) return 0;
    vector<ll> y(16);
    int r = (n - 5) % 2, N = (n - 5) / 2;
    FOR(i,0,15) y[i] = calc(2*i + 5 + r);
    return LagrangeInterpolation(y, N);
}

void init() {
    f[0] = 1;
    rev[0] = inv(f[0]);
    FOR(i,1,200) {
        f[i] = mul(f[i-1], i);
        rev[i] = inv(f[i]);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    init();
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << solve(n) << "\n";
    }
    return 0;
}
