#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
const int MOD = 1000000007;
struct Mint {
	int val;
	Mint() { val = 0; }
	Mint(const ll& x) {
		val = (-MOD <= x && x < MOD) ? x : x % MOD;
		if (val < 0) val += MOD;
	}
	template <typename U>
	explicit operator U() const { return (U)val; }
	friend bool operator==(const Mint& a, const Mint& b) { return a.val == b.val; }
	friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
	friend bool operator<(const Mint& a, const Mint& b) { return a.val < b.val; }
	Mint& operator+=(const Mint& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
	Mint& operator-=(const Mint& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
	Mint& operator*=(const Mint& m) { val = (ll)val * m.val % MOD; return *this; }
	friend Mint modex(Mint a, ll p) {
		assert(p >= 0);
		Mint ans = 1;
		for (; p; p >>= 1, a *= a) if (p & 1) ans *= a;
		return ans;
	}
	Mint& operator/=(const Mint& m) { return *this *= modex(m, MOD - 2); }
	Mint& operator++() { return *this += 1; }
	Mint& operator--() { return *this -= 1; }
	Mint operator++(int) { Mint result(*this); *this += 1; return result; }
	Mint operator--(int) { Mint result(*this); *this -= 1; return result; }
	Mint operator-() const { return Mint(-val); }
	friend Mint operator+(Mint a, const Mint& b) { return a += b; }
	friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
	friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
	friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
	friend ostream& operator<<(ostream& os, const Mint& x) { return os << x.val; }
};
template <typename T>
vector<T> multiply(const vector<T>& a, const vector<T>& b) {
	if (a.empty() || b.empty()) return {};
	vector<T> c(a.size() + b.size() - 1);
	for (int i = 0; i < a.size(); ++i)
		for (int j = 0; j < b.size(); ++j)
			c[i + j] += a[i] * b[j];
	return c;
}
template <typename T>
vector<T> inverse(const vector<T>& a) {
	assert(!a.empty() && a[0] != 0);
	int n = a.size();
	vector<T> b(n);
	b[0] = 1 / a[0];
	for (int i = 1; i < n; ++i) {
		for (int j = i - 1; j >= 0; --j) {
			b[i] -= b[j] * a[i - j];
		}
	}
	return b;
}
template <typename T>
vector<T> remainder(vector<T> a, const vector<T>& b) {
	int bs = b.size();
	assert(b[bs - 1] != 0);
	T invb = 1 / b[bs - 1];
	for (int i = (int)a.size() - 1; i >= bs - 1; --i) {
		T mult = -a[i] * invb;
		for (int j = i; j > i - bs; --j) {
			a[j] += mult * b[bs - 1 - (i - j)];
		}
	}
	while (!a.empty() && a.back() == 0) a.pop_back();
	return a;
}
/* Find x^p mod md in O(deg(md)^2 log p). */
template <typename T>
vector<T> expx(ll p, const vector<T>& md) {
	if (!p) return md.size() == 1 ? vector<T>{} : vector<T>{1};
	if (p & 1) {
		auto q = expx(p - 1, md);
		q.insert(q.begin(), 0);
		return remainder(q, md);
	}
	auto q = expx(p >> 1, md);
	q = multiply(q, q);
	return remainder(q, md);
}
int main() {
	vector<Mint> p = {1, -1}, q = {1, 0, -1}, denom = {1};
	for (int i = 0; i < 11; ++i) {
		denom = multiply(denom, p);
	}
	for (int i = 0; i < 5; ++i) {
		denom = multiply(denom, q);
	}
	// Find first 20 values.
	auto vals = inverse(denom);
	reverse(denom.begin(), denom.end());
	int T;
	scanf("%d", &T);
	while (T--) {
		int n;
		scanf("%d", &n);
		n -= 5;
		if (n < 0) {
			printf("0\n");
			continue;
		}
		auto res = expx(n, denom);
		Mint ans = 0;
		for (int i = 0; i < res.size(); ++i) {
			ans += vals[i] * res[i];
		}
		printf("%d\n", ans.val);
	}
}


Measured memory_bytes: 3760