#include <cstdio>
#include <cstring>

const int d[200] = {1, 272, 589185, 930336768, 853401154, 217676188, 136558333, 415722813, 985269529, 791527976, 201836136, 382110354, 441223705, 661537677, 641601343, 897033284, 816519670, 365311407, 300643484, 936803543, 681929467, 462484986, 13900203, 657627114, 96637209, 577140657, 600647073, 254604056, 102389682, 811580173, 592550067, 587171680, 526467503, 265885773, 951722780, 219627841, 371508152, 283501391, 159234514, 439380999, 722868959, 125599834, 351398134, 456317548, 365496182, 614778702, 502680047, 193063685, 309004764, 743901785, 870955115, 312807829, 160375015, 691844624, 137034372, 350330868, 895680450, 282610535, 317897557, 28600551, 583305647, 539409363, 327406961, 627805385, 680183978, 681299085, 954964592, 743524009, 788048339, 699454626, 666369521};
const int a[200] = {0, 1751, 999883602, 914547334, 445884965, 843985763, 651949738, 172854420, 500637785, 764979556, 54753727, 512476630, 818187525, 194269, 218332258, 843980077, 512995938, 834951442, 776083750, 431452571, 733916043, 834563135, 293320091, 961071575, 222318523, 224646235, 790449034, 65115950, 350840686, 273883603, 961824651, 743754019, 847316445, 100093489, 917653052, 755269619, 244730388, 82346955, 899906518, 152683562, 256245988, 38175356, 726116404, 649159321, 934884057, 209550973, 775353772, 777681484, 38928432, 706679916, 165436872, 266083964, 568547436, 223916257, 165048565, 487004069, 156019930, 781667749, 999805738, 181812482, 487523377, 945246280, 235020451, 499362222, 827145587, 348050269, 156014244, 554115042, 85452673, 116405, 999998256, 1};
const int m = 71;
int b[32][200], bb;
int c[200];
int p = 1000000007;
int t, n;
inline int mul(int x, int y) {
	return (long long)x * y % p;
}
void mul(const int c[], const int b[], int re[]) {
	int w[200] = {};
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			w[i + j] = (w[i + j] + mul(c[i], b[j]));
			if (w[i + j] >= p) {
				w[i + j] -= p;
			}
		}
	}

	for (int i = 2 * m - 2; i >= m; i--) {
		for (int k = 1; k <= m; k++) {
			w[i - k] = (w[i - k] + mul(w[i], a[k]));
			if (w[i - k] >= p) {
				w[i - k] -= p;
			}
		}
	}

	for (int i = 0; i < m; i++) {
		re[i] = w[i];
	}
}
int main() {
	b[0][1] = 1;
	for (scanf("%d", &t); t--;) {
		memset(c, 0, sizeof c);
		c[0] = 1;
		scanf("%d", &n);
		for (int k = 0; n;) {
			if (n & 1) {
				mul(c, b[k], c);
			}
			if (!(n >>= 1)) {
				break;
			}
			if (k == bb) {
				bb++;
				mul(b[k], b[k], b[k + 1]);
			}
			k++;
		}
		int ans = 0;
		for (int i = 0; i < m; i++) {
			ans = (ans + mul(c[i], d[i]));
			if (ans >= p) {
				ans -= p;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}