// Slower C++ solution:
#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'



constexpr ll mod = 1000000007LL;

constexpr ll v_e[] = { 869418286, 727008098, 660103155, 183023413, 471090892, 417297686, 237315285, 542573865, 444014759, 927321758, 184117322, 5655049, 347662323, 346175634, 765144583, 0 };

constexpr ll v_o[] = { 869418286, 727008098, 660103155, 183023413, 471090892, 417297686, 237315285, 542573865, 444014759, 927321758, 184117322, 962779130, 404391958, 700407153, 729548371, 539588932 };



int main() {

	ios::sync_with_stdio(false);

	std::cin.tie(0);



	ll T, N, N2, N4, N8; cin >> T;

	ll ans0, ans4,ans8, ans12;

	for (int _t = 0; _t < T; _t++) {

		cin >> N;

		N2 = (N * N) % mod;

		N4 = (N2 * N2) % mod;

		N8 = (N4 * N4) % mod;



		if (N & 1) {// odd

			ans0 = (((v_o[0] * N + v_o[1]) % mod) * N2 + ((v_o[2] * N + v_o[3]) % mod)) % mod;

			ans4 = (((v_o[4] * N + v_o[5]) % mod) * N2 + ((v_o[6] * N + v_o[7]) % mod)) % mod;

			ans8 = (((v_o[8] * N + v_o[9]) % mod) * N2 + ((v_o[10] * N + v_o[11]) % mod)) % mod;

			ans12 = (((v_o[12] * N + v_o[13]) % mod) * N2 + ((v_o[14] * N + v_o[15]) % mod)) % mod;



			cout << (((ans0 * N4 + ans4) % mod) * N8 + ((ans8 * N4 + ans12) % mod)) % mod << endl;

		}

		else {// even

			ans0 = (((v_e[0] * N + v_e[1]) % mod) * N2 + ((v_e[2] * N + v_e[3]) % mod)) % mod;

			ans4 = (((v_e[4] * N + v_e[5]) % mod) * N2 + ((v_e[6] * N + v_e[7]) % mod)) % mod;

			ans8 = (((v_e[8] * N + v_e[9]) % mod) * N2 + ((v_e[10] * N + v_e[11]) % mod)) % mod;

			ans12 = (((v_e[12] * N + v_e[13]) % mod) * N2 + ((v_e[14] * N + v_e[15]) % mod)) % mod;



			cout << (((ans0 * N4 + ans4) % mod) * N8 + ((ans8 * N4 + ans12) % mod)) % mod << endl;

		}

	}



	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.208276778664651x):
#include <stdio.h>



typedef long long ll;



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

constexpr ll mod = 1000000007;



class modlong {

public:

	modlong(ll num) { x = num; }

	inline operator ll() const { return x; }

	inline void operator = (ll num) { x = num; }

	inline void operator += (ll num) { x += num; }

	inline void operator *= (ll num) { x = adjust(x * num); }

	inline modlong operator * (ll num) { modlong m(adjust(x * num)); return m; }

	inline ll adjust(ll a) {

		if (a >= mod) { return a % mod; }

		return a;

	}

	ll x;

};



constexpr int K = 16;



constexpr ll v_e[] = { 0, 765144583, 346175634, 347662323, 5655049, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };

constexpr ll v_o[] = { 539588932, 729548371, 700407153, 404391958, 962779130, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };



int main() {

	int T; scanf("%d", &T);

	for (int _t = 0; _t < T; _t++) {

		ll N; scanf("%ld", &N);

		modlong ans = 0;

		modlong x = 1;



		if (N & 1) {// odd

			for (int i = 0; i < K; i++) {

				ans += x * v_o[i];

				x *= N;

			}

		}

		else {// even

			for (int i = 0; i < K; i++) {

				ans += x * v_e[i];

				x *= N;

			}

		}

		printf("%ld\n", ans.x % mod);

	}



	return 0;

}