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

template <int MOD_> struct modnum {
	static constexpr int MOD = MOD_;
	static_assert(MOD_ > 0, "MOD must be positive");

private:
	using ll = long long;

	int v;

	static int minv(int a, int m) {
		a %= m;
		assert(a);
		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
	}

public:

	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int() const { return v; }
	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }

	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

	modnum inv() const {
		modnum res;
		res.v = minv(v, MOD);
		return res;
	}
	friend modnum inv(const modnum& m) { return m.inv(); }
	modnum neg() const {
		modnum res;
		res.v = v ? MOD-v : 0;
		return res;
	}
	friend modnum neg(const modnum& m) { return m.neg(); }

	modnum operator- () const {
		return neg();
	}
	modnum operator+ () const {
		return modnum(*this);
	}

	modnum& operator ++ () {
		v ++;
		if (v == MOD) v = 0;
		return *this;
	}
	modnum& operator -- () {
		if (v == 0) v = MOD;
		v --;
		return *this;
	}
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= o.inv();
	}

	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};

template <typename T> T pow(T a, long long b) {
	assert(b >= 0);
	T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
}

using num = modnum<int(1e9) + 7>;

vector<num> fact, ifact;

void init() {
	const int N = 123;
	fact.resize(N);
	fact[0] = 1;
	for (int i = 1; i < N; i++) fact[i] = fact[i-1] * i;
	ifact.resize(N);
	ifact.back() = inv(fact.back());
	for (int i = N-1; i >= 1; i--) ifact[i-1] = ifact[i] * i;
}

num ncr(int n, int r) {
	return fact[n] * ifact[r] * ifact[n-r];
}

num eval(const vector<num>& poly, num x) {
	num res = 0;
	for (int i = int(poly.size())-1; i >= 0; i--) {
		res = res * x + poly[i];
	}
	return res;
}

num f(int n) {
	num res = 0;
	for (int i = 0; 2*i+5 <= n; i++) {
		res += ncr(i+4, 4) * ncr(n-2*i+5, 10);
	}
	return res;
}

vector<num> interpolate(const vector<num>& X, const vector<num>& Y) {
	int N = int(X.size());
	vector<num> prod(N+1);
	prod[0] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = i; j >= 0; j--) {
			prod[j+1] += prod[j];
			prod[j] *= -X[i];
		}
	}
	vector<num> res(N);
	for (int i = 0; i < N; i++) {
		if (int(X[i])) {
			num xinv = num(1) / (-X[i]);
			for (int j = 0; j < N; j++) {
				prod[j] *= xinv;
				prod[j+1] -= prod[j];
			}
		} else {
			assert(!int(prod[0]));
			for (int j = 0; j < N; j++) {
				prod[j] = prod[j+1];
			}
		}
		num extra = 1;
		for (int j = 0; j < N; j++) {
			if (i != j) {
				extra *= X[i] - X[j];
			}
		}
		extra = num(1) / num(extra);
		extra *= Y[i];
		for (int j = 0; j < N; j++) {
			res[j] += extra * prod[j];
		}
		for (int j = N-1; j >= 0; j--) {
			prod[j+1] += prod[j];
			prod[j] *= -X[i];
		}
	}
	return res;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	init();
	vector<num> polys[2];
	for (int z = 0; z < 2; z++) {
		vector<num> xs, ys;
		for (int x = 0; x <= 15; x++) {
			xs.push_back(x);
			ys.push_back(f(2*x+5+z));
		}
		polys[z] = interpolate(xs, ys);
	}
	int q;
	cin >> q;
	for (int j = 0; j < q; j++) {
		int n;
		cin >> n;
		if (n <= 4) {
			cout << 0 << '\n';
		} else {
			cout << eval(polys[(n-5)%2], (n-5)/2) << '\n';
		}
	}
}


Measured memory_bytes: 3672