#include <iostream>
using namespace std;
 
int main() {
 
	long long mod = 1e9+7;
	long long n2 = 1e6+6;
	long long DP[n2][3];
 
	DP[1][1]=1;
	DP[1][2]=1;
 
	for(long long i=2;i<=n2;i++)
	{
		DP[i][1] = ((4*DP[i-1][1])%mod + DP[i-1][2]%mod)%mod;
		DP[i][2] = (DP[i-1][1] + (2*DP[i-1][2])%mod)%mod;
	}
 
	long long T;
	cin>>T;
 
	while(T--)
	{
		long long n;
		cin>>n;
 
		//cout<<"n="<<n<<endl;
 
		cout<<(DP[n][1]+DP[n][2])%mod<<endl;
	}
 
 
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CgoJbG9uZyBsb25nIG1vZCA9IDFlOSs3OwoJbG9uZyBsb25nIG4yID0gMWU2KzY7Cglsb25nIGxvbmcgRFBbbjJdWzNdOwoJCQoJRFBbMV1bMV09MTsKCURQWzFdWzJdPTE7CgkKCWZvcihsb25nIGxvbmcgaT0yO2k8PW4yO2krKykKCXsKCQlEUFtpXVsxXSA9ICgoNCpEUFtpLTFdWzFdKSVtb2QgKyBEUFtpLTFdWzJdJW1vZCklbW9kOwoJCURQW2ldWzJdID0gKERQW2ktMV1bMV0gKyAoMipEUFtpLTFdWzJdKSVtb2QpJW1vZDsKCX0KCQoJbG9uZyBsb25nIFQ7CgljaW4+PlQ7CgkKCXdoaWxlKFQtLSkKCXsKCQlsb25nIGxvbmcgbjsKCQljaW4+Pm47CgkKCQkvL2NvdXQ8PCJuPSI8PG48PGVuZGw7CgkKCQljb3V0PDwoRFBbbl1bMV0rRFBbbl1bMl0pJW1vZDw8ZW5kbDsKCX0KCQoJCgkKCXJldHVybiAwOwp9

MwoyCjYKMTMzNwo=

3
2
6
1337