#include<iostream>
#include<stack>
#include<string.h>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<climits>
#include<cstdio>
using namespace std;
const int M = 1e9 + 7;
int t, l[101], n = 1, xam;
long long a[45000][4][4], b[4][4] = { {0, 0, 0, 0}, {0, 1, 0, 1}, {0, 1, 1, 1}, {0, 1, 1, 2} }, c[4][4], res, ans[4][4];
void f(int x)
{
	if (x <= 3)
	{
		printf("1\n");
		return;
	}
	int y = (x-1) / 3, p = 1;
	for (int i = 1; i <= 3; ++i)
		ans[i][i] = 1;
	while (y)
	{
		if (y & 1)
		{
			for (int i = 1; i <= 3; ++i)
				for (int j = 1; j <= 3; ++j)
					for (int k = 1; k <= 3; ++k)
						c[i][j] = (c[i][j] + ans[i][k] * a[p][k][j] % M) % M;
			for (int i = 1; i <= 3; ++i)
			{
				for (int j = 1; j <= 3; ++j)
				{
					ans[i][j] = c[i][j];
					c[i][j] = 0;
				}
			}
		}
		++p;
		y >>= 1;
	}
	res = 0;
	p = (x - 1) % 3 + 1;
	for (int i = 1; i <= 3; ++i)
		res = (res + ans[p][i]) % M;
	printf("%lld\n", res);
	memset(ans, 0, sizeof(ans));
}
int main()
{
	scanf("%d", &t);
	for (int i = 1; i <= t; ++i)
	{
		scanf("%d", &l[i]);
		xam = max(xam, l[i]);
	}
	for (int i = 1; i <= 3; ++i)
		for (int j = 1; j <= 3; ++j)
			a[1][i][j] = b[i][j];
	for (int i = 2, e = log2((xam) / 3)+1; i <= e; ++i)
	{
		for (int j = 1; j <= 3; ++j)
			for (int k = 1; k <= 3; ++k)
				for (int p = 1; p <= 3; ++p)
					a[i][j][k] = (a[i][j][k] + a[i-1][j][p] * a[i-1][p][k] % M) % M;
	}
	for (int i = 1; i <= t; ++i)
	{
		f(l[i]);
	}
	return 0;
}

测评时爆零，然后把第一个测试点下载下来了，在本地和洛谷ide都是正确的，结果一测评就报零