#include <stdio.h>
#define MOD 1000000007ULL

unsigned long long a[2], temp[2], b[2][2], temp1[2][2], n;

void solve()
{
	a[0] = 2;
	a[1] = 1;
	b[0][0] = 2;
	b[0][1] = 1;
	b[1][0] = 1;
	b[1][1] = 1;
	while(n>0)
	{
		if(n&1)
		{
			temp[0] = a[0]*b[0][0] + a[1]*b[1][0];
			temp[1] = a[0]*b[0][1] + a[1]*b[1][1];
			a[0] = temp[0]%MOD;
			a[1] = temp[1]%MOD;
		}
		temp1[0][0] = b[0][0]*b[0][0] + b[0][1]*b[1][0];
		temp1[0][1] = b[0][0]*b[0][1] + b[0][1]*b[1][1];
		temp1[1][0] = b[1][0]*b[0][0] + b[1][1]*b[1][0];
		temp1[1][1] = b[1][0]*b[0][1] + b[1][1]*b[1][1];
		b[0][0] = temp1[0][0]%MOD;
		b[0][1] = temp1[0][1]%MOD;
		b[1][0] = temp1[1][0]%MOD;
		b[1][1] = temp1[1][1]%MOD;
		n = n>>1;
	}
}

int main()
{
	unsigned int t;
	scanf("%u", &t);
	while(t--)
	{
		scanf("%lld", &n);
		n = n - 1ULL;
		solve();
		printf("%llu\n", (a[0]*a[1])%MOD);
	}
}