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

// #define int long long // intで書いたけど心配なときにlong longに変換する
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)
#define X real()
#define Y imag()

/* REPmacro */
#define REPS(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (ll i = (a); i >= (ll)(n); --i)
#define DEP(i, n) DEPS(i, n, 0)
#define EACH(i, n) for (auto&& i : n)

/* debug */
#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

/* alias */
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using plglg = pair<ll, ll>;
using tlglglg = tuple<ll, ll, ll>;
using D = double;
using P = complex<D>;
using vs = vector<string>;
template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; cin >> x; return x;}
inline ll IN() {ll x; cin >> x; return x;}
inline vs split(const string& t, char c) {vs v; stringstream s(t); string b; while(getline(s, b, c)) v.eb(b); return v;}
template <typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
template <typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
template <typename T, typename S> inline void print(const pair<T, S>& p) {cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << endl;}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v) {for (auto&& p : v) print(p);}
template <typename T> inline void print(const vector<T>& v, string s = " ") {REP(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}
inline void yesno(bool ok, string yes = "Yes", string no = "No") {cout << (ok?yes:no) << endl;}


// ll mod = 1000000007;

// ll modplus(ll x, ll y) {
//     return (x + y) % mod;
// }

// ll modminus(ll x, ll y) {
//     return (x - y + mod) % mod;
// }

// ll multiply(ll x, ll y) {
//     return (x % mod) * (y % mod) % mod;
// }

// ll m;
// vll modmatmul(vll &dp, vvll &mt) {
//     vll ret(m, 0LL);
//     REP(i, m) REP(j, m) ret[i] = modplus(ret[i], multiply(mt[i][j], dp[j]));
//     return ret;
// }

// vvll modupdate(vvll &mt) {
//     vvll ret(m, vll(m, 0LL));
//     REP(i, m) REP(j, m) REP(k, m) ret[i][j] = modplus(ret[i][j], multiply(mt[i][k], mt[k][j]));
//     return ret;
// }

// void modmatpow(vll &dp, vvll &mt, ll k) {
//     ll m = dp.size();
//     while(k) {
//         // if(k & 1) dp = modmatmul(dp, mt);
//         if (k & 1) {
//             vll ret(m, 0LL);
//             REP(i, m) REP(j, m) ret[i] = modplus(ret[i], multiply(mt[i][j], dp[j]));
//             dp = ret;
//         }
//         // mt = modupdate(mt);
//         vvll ret(m, vll(m, 0LL));
//         REP(i, m) REP(j, m) REP(k, m) ret[i][j] = modplus(ret[i][j], multiply(mt[i][k], mt[k][j]));
//         mt = ret;
//         k /= 2;
//     }
// }

int mod = 1000000007;
int add(int x, int y) { return (x += y) >= mod ? x - mod : x; }
template<class... T> int add(int x, T... y) { return add(x, add(y...)); }
int mul(int x, int y) { return 1LL * x * y % mod; }
template<class... T> int mul(int x, T... y) { return mul(x, mul(y...)); }
int sub(int x, int y) { return add(x, mod - y); }
int modpow(int a, long long b) {
	int ret = 1; while (b > 0) {
		if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod; b >>= 1;
	} return ret;
}
int modinv(int a) { return modpow(a, mod - 2); }
typedef vector<int> Vec;
typedef vector<Vec> Mat;
Vec mulMatVec(Mat a, Vec b)
{
	int n = b.size(); Vec ret(n, 0);
	REPS(i, 0, n) REPS(j, 0, n) ret[i] = add(ret[i], mul(a[i][j], b[j]));
	return ret;
}
Mat mulMatMat(Mat a, Mat b)
{
	int n = a.size(); Mat ret(n, Vec(n, 0));
	REPS(i, 0, n) REPS(j, 0, n) REPS(k, 0, n) ret[i][j] = add(ret[i][j], mul(a[i][k], b[k][j]));
	return ret;
}
Mat fastpow(Mat x, ll n)
{
	Mat ret(x.size(), Vec(x.size(), 0));
	REPS(i, 0, x.size()) ret[i][i] = 1;
	while (0 < n) { if ((n % 2) == 0) { x = mulMatMat(x, x); n >>= 1; } else { ret = mulMatMat(ret, x); --n; } }
	return ret;
}
void printVec(Vec a) { cout << "[\t"; REPS(i, 0, a.size()) cout << a[i] << "\t"; cout << "]" << endl; }
void printMat(Mat a) { REPS(i, 0, a.size()) printVec(a[i]); }

void solve() {
    ll n; cin >> n;

    if (n < 5) {
        print(0);
        return;
    }

    Vec dp(32, 0);
    Mat mt(32, Vec(32, 0));

    // REP(i, 16) {
    //     if (i >= 5) {
    //         dp[2*i] = 1LL;
    //     }
    // }

    dp[0] = 1;

    // REP(i, 16) {
    //     mt[2*i+0][2*i+1] = 1LL;
    //     mt[2*i+1][2*i+0] = 1LL;

    //     if (1 <= i && i <= 5) {
    //         REP(j, i) {
    //             mt[2*i+0][2*j+1] = 1LL;
    //         }
    //     } else if (6 <= i) {
    //         REP(j, i) {
    //             mt[2*i+0][2*j+0] = 1LL;
    //             mt[2*i+0][2*j+1] = 1LL;
    //         }
    //     }
    // }
    REP(group, 16) REP(p, 2) {
        mt[group*2 + 1-p][group*2 + p] += 1;
        if (group < 5 && p == 1) continue;
        REPS(dest, group+1, 16) mt[dest*2 + 1][group*2 + p] += 1;
    }

    // print("=====");
    // print(dp);
    // print("-----");
    // REP(i, 32) print(mt[i]);

    // modmatpow(dp, mt, n-5);
    // ll m = 32;
    // ll k = n-4;  // dp[0]=1LLから1の操作で初期状態にしてからn-5回繰り返すのでk=n-4
    // vll ret1(m, 0LL);
    // vvll ret2(m, vll(m, 0LL));
    // while(k) {
    //     // if(k & 1) dp = modmatmul(dp, mt);
    //     if (k & 1) {
    //         REP(i, m) ret1[i] = 0LL;
    //         REP(i, m) REP(j, m) ret1[i] = modplus(ret1[i], multiply(mt[i][j], dp[j]));
    //         REP(i, m) dp[i] = ret1[i];
    //     }
    //     // mt = modupdate(mt);
    //     REP(i, m) REP(j, m) ret2[i][j] = 0LL;
    //     REP(i, m) REP(j, m) REP(k, m) ret2[i][j] = modplus(ret2[i][j], multiply(mt[i][k], mt[k][j]));
    //     REP(i, m) REP(j, m) mt[i][j] = ret2[i][j];
    //     k /= 2;
    // }

    mt = fastpow(mt, n-4);
    dp = mulMatVec(mt, dp);

    ll ans = add(dp[30], dp[31]);
    print(ans);
}

signed main() {
    //my-code
    ll t; cin >> t;

    REP(i, t) solve();

    return 0;
}

// https://github.com/kurokoji/.cpp-Template/wiki テンプレートについて
// http://www.creativ.xyz/dump-cpp-652 dump()について
// https://gist.github.com/rigibun/7905920 色々

Measured memory_bytes: 3700