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

const ll mod = 1000000007LL;

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

	constexpr int K = 16;

	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 };

	ll T, N; cin >> T;
	for (int _t = 0; _t < T; _t++) {
		cin >> N;
		ll ans = v_e[0];
		if (N & 1) {// odd
			for (int i = 1; i < K; i++) {
				ans = ans * N + v_o[i];
				if(ans >= mod) ans %= mod;
			}
		}
		else {// even
			for (int i = 1; i < K; i++) {
				ans = ans * N + v_e[i];
				if (ans >= mod) ans %= mod;
			}
		}
		cout << ans << endl;
	}

	return 0;
}
