// Original C++ solution (slower):
#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>;



template <typename num>

std::vector<num> BerlekampMassey(const std::vector<num>& s) {

	int n = int(s.size()), L = 0, m = 0;

	std::vector<num> C(n), B(n), T;

	C[0] = B[0] = 1;



	num b = 1;

	for(int i = 0; i < n; i++) { ++m;

		num d = s[i];

		for (int j = 1; j <= L; j++) d += C[j] * s[i - j];

		if (d == 0) continue;

		T = C; num coef = d / b;

		for (int j = m; j < n; j++) C[j] -= coef * B[j - m];

		if (2 * L > i) continue;

		L = i + 1 - L; B = T; b = d; m = 0;

	}



	C.resize(L + 1); C.erase(C.begin());

	for (auto& x : C) {

		x = -x;

	}

	return C;

}



template <typename num>

num linearRec(const std::vector<num>& S, const std::vector<num>& tr, long long k) {

	int n = int(tr.size());

	assert(S.size() >= tr.size());



	auto combine = [&](std::vector<num> a, std::vector<num> b) {

		std::vector<num> res(n * 2 + 1);

		for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) res[i + j] += a[i] * b[j];

		for (int i = 2 * n; i > n; --i) for (int j = 0; j < n; j++)

			res[i - 1 - j] += res[i] * tr[j];

		res.resize(n + 1);

		return res;

	};



	std::vector<num> pol(n + 1), e(pol);

	pol[0] = e[1] = 1;



	for (++k; k; k /= 2) {

		if (k % 2) pol = combine(pol, e);

		e = combine(e, e);

	}



	num res = 0;

	for (int i = 0; i < n; i++) res += pol[i + 1] * S[i];

	return res;

}



int main() {

	ios::sync_with_stdio(0), cin.tie(0);

	vector<num> terms{0,0,0,0,0,1,11,71,341,1346,4598,14038,39138,101193,245443,563447,1232837,2585672,5222552,10198232,19316488,35588718,63933498,112225058,192839398,324900532,537499132,874246012,399637805,207858088,434820093,274485959,780358,996765147,793168065,118878018,966647141,677996797,52230779,485540255,147468710,203524158,94513877};

	cerr << terms.size() << endl;

	vector<num> tr = BerlekampMassey(terms);

	int q;

	cin >> q;

	for (int j = 0; j < q; j++) {

		int n;

		cin >> n;

		cout << linearRec(terms, tr, n) << '\n';

	}

}


// Optimized solution to the same problem (faster):
#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';

		}

	}

}


// Fastest known solution for this problem: