#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>
#include <complex>
#include <assert.h>

using namespace std;
typedef long long ll;
#define endl '\n'

template<typename T>
inline bool chmin(T& x, T a) {
	if (x >= a) { x = a; return true; }
	return false;
}

template<typename T>
inline bool chmax(T& x, T a) {
	if (x <= a) { x = a; return true; }
	return false;
}

/////////////         modの計算

#define MOD_IS_PRIME
const ll mod = 1000000007LL;

class modlong {
public:
	modlong() { x = 0; }
	modlong(ll num) { x = adjust(num); }
	inline operator ll() const { return x; }
	inline bool operator ==(ll num) { return this->x == num; }
	inline bool operator !=(ll num) { return !(*this == num); }
	inline void operator = (ll num) { x = adjust(num); }
	inline void operator += (ll num) { x = adjust(x + num); }
	inline void operator ++() { this->operator+=(1); }
	inline modlong operator + (ll num) const { modlong m(this->x); m += num; return m; }
	inline void operator -= (ll num) { x = adjust(x - num); }
	inline void operator --() { this->operator-=(1); }
	inline modlong operator - (ll num) { modlong m(this->x); m -= num; return m; }
	inline void operator *= (ll num) { x = adjust(x * num); }
	inline modlong operator * (ll num) { modlong m(this->x); m *= num; return m; }
	inline void operator /= (ll num);
	inline modlong operator / (ll num);
private:
	inline ll adjust(ll a) {
		if (a >= mod) { return a % mod; }
		if (a < 0) { return mod - 1 + ((a + 1) % mod); }
		return a;
	}
	ll x;
};
inline modlong mod_inv(modlong a) {
	const ll inv_max = 300000;
	static vector<ll> inv;
	if (inv.size() == 0) {
		inv.resize(inv_max);
		for (int i = 0; i < inv_max; i++) {
			if (i <= 1) { inv[i] = i; }
			else { inv[i] = ((mod - mod / i) * inv[mod % i]) % mod; }
		}
	}
	ll p = mod, q = a, r;
	modlong m = 0, n = 1, c;
	while (1) {
		if (q < inv_max) { return n * inv[q]; }
		c = p / q; r = p % q; c = m - n * c;
		p = q, q = r; m = n, n = c;
	}
}
inline modlong mod_div(modlong a, modlong b) { return a * mod_inv(b); }
inline void modlong::operator /=(ll num) { x = mod_div(*this, num); }
inline modlong modlong::operator /(ll num) { modlong m(this->x); m /= num; return m; }

inline modlong mod_pow(modlong x, ll n) {
	if (n < 0) { x = mod_inv(x); n = -n; }
#ifdef MOD_IS_PRIME
	n = n % (mod - 1);
#endif
	modlong temp = x, ans = 1;
	while (n > 0) {
		if (n & 1) { ans *= temp; }
		temp *= temp;
		n >>= 1;
	}
	return ans;
}
inline modlong mod_log(modlong a, modlong x) {
	ll A = sqrt(mod);
	ll B = (mod + A - 1) / A;
	map<ll, ll> mp1, mp2;
	ll p0 = a;
	ll q0 = mod_pow(a, -A);
	ll p = 1;
	ll q = x;
	for (int i = 0; i < A; i++) {
		mp1.insert({ p, i });
		p = (p * p0) % mod;
	}
	for (int i = 0; i < B; i++) {
		mp2.insert({ q, A * i });
		q = (q * q0) % mod;
	}
	auto itr1 = mp1.begin();
	auto itr2 = mp2.begin();
	while (itr1 != mp1.end() && itr2 != mp2.end()) {
		if (itr1->first < itr2->first) {
			itr1++;
		}
		else if (itr1->first == itr2->first) {
			return itr1->second + itr2->second;
		}
		else {
			itr2++;
		}
	}
	return 0;
}

inline modlong mod_factorial(modlong n, bool inverse = false) {
	static vector<ll> factorial, factorial_inv;

	ll M = factorial.size();
	if (M <= n) {
		if (M == 0) { factorial.push_back(1); factorial_inv.push_back(1); M++; }
		if (M == 1) { factorial.push_back(1); factorial_inv.push_back(1); M++; }

		for (ll i = M; i <= n; i++) {
			factorial.push_back((factorial.back() * i) % mod);
			factorial_inv.push_back((factorial_inv.back() * mod_inv(i)) % mod);
		}
	}
	if (inverse == true) { return factorial_inv[n]; }
	else { return factorial[n]; }
}
inline modlong mod_combination(modlong n, modlong r) {
	assert(r <= n);
	return mod_factorial(n) * mod_factorial(n - r, true) * mod_factorial(r, true);
}

modlong func(ll x) {
	return ((x + 1) / 2) * ((x + 2) / 2);
}

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

	constexpr int K = 20;

	vector<pair<modlong, modlong>> sample_o, sample_e;
	for (int i = 1; i < K * 2; i += 2) {
		modlong a = 0;
		for (int s = 1; s <= i; s++) {
			for (int n = 1; n <= i - s; n++) {
				for (int u = 1; u <= i - s - n; u++) {
					for (int k = 1; k <= i - s - n - u; k++) {
						for (int e = 1; e <= i - s - n - u - k; e++) {
							a += func(s) * func(n) * func(u) * func(k) * func(e);
						}
					}
				}
			}
		}
		sample_o.push_back({ i, a });
	}
	for (int i = 0; i < K * 2; i += 2) {
		modlong a = 0;
		for (int s = 1; s <= i; s++) {
			for (int n = 1; n <= i - s; n++) {
				for (int u = 1; u <= i - s - n; u++) {
					for (int k = 1; k <= i - s - n - u; k++) {
						for (int e = 1; e <= i - s - n - u - k; e++) {
							a += func(s) * func(n) * func(u) * func(k) * func(e);
						}
					}
				}
			}
		}
		sample_e.push_back({ i, a });
	}

	
	vector<modlong> c_o(K + 1, 0), c_e(K + 1, 0);

	for (int k = 0; k < sample_o.size(); k++) {
		vector<modlong> base_o(K + 1, 0), base_e(K + 1, 0);
		base_o[0] = 1, base_e[0] = 1;
		modlong x0 = sample_o[k].first, y0 = sample_o[k].second;
		modlong m = y0;

		for (int i = 0; i < sample_o.size(); i++) {
			if (i == k) { continue; }
			modlong x = sample_o[i].first, y = sample_o[i].second;
			m /= (x0 - x);

			for (int j = K - 1; j >= 0; j--) {
				base_o[j + 1] = base_o[j];
			}
			base_o[0] = 0;
			for (int j = 0; j < K; j++) {
				base_o[j] -= x * base_o[j + 1];
			}
		}

		for (int i = 0; i < K + 1; i++) {
			c_o[i] += base_o[i] * m;
		}
	}
	for (int k = 0; k < sample_e.size(); k++) {
		vector<modlong> base_o(K + 1, 0), base_e(K + 1, 0);
		base_o[0] = 1, base_e[0] = 1;
		modlong x0 = sample_e[k].first, y0 = sample_e[k].second;
		modlong m = y0;

		for (int i = 0; i < sample_e.size(); i++) {
			if (i == k) { continue; }
			modlong x = sample_e[i].first, y = sample_e[i].second;
			m /= (x0 - x);

			for (int j = K - 1; j >= 0; j--) {
				base_e[j + 1] = base_e[j];
			}
			base_e[0] = 0;
			for (int j = 0; j < K; j++) {
				base_e[j] -= x * base_e[j + 1];
			}
		}

		for (int i = 0; i < K + 1; i++) {
			c_e[i] += base_e[i] * m;
		}
	}

	int T; cin >> T;
	for (int _t = 0; _t < T; _t++) {
		ll N; cin >> N;
		if (N % 2 == 0) {// even
			modlong ans = 0;
			for (int i = 0; i < c_e.size(); i++) {
				ans += mod_pow(N, i) * c_e[i];
			}
			cout << (ll)ans << endl;
		}
		else {// odd
			modlong ans = 0;
			for (int i = 0; i < c_o.size(); i++) {
				ans += mod_pow(N, i) * c_o[i];
			}
			cout << (ll)ans << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 4892