#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'

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

#define MOD_IS_PRIME
constexpr ll mod = 1000000007LL;

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

	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 T; cin >> T;
	for (int _t = 0; _t < T; _t++) {
		ll N; cin >> N;
		if (N % 2 == 0) {// even
			ll ans = 0;
			ll x = 1;
			for (int i = 0; i < K; i++) {
				ans += (x * v_e[i]) % mod;
				x = (x * N) % mod;
			}
			cout << ans % mod << endl;
		}
		else {// odd
			ll ans = 0;
			ll x = 1;
			for (int i = 0; i < K; i++) {
				ans += (x * v_o[i]) % mod;
				x = (x * N) % mod;
			}
			cout << ans % mod << endl;
		}
	}

	return 0;
}