#include <iostream>
#define max 1000000007
using namespace std;
int schemes(int n) {
int a[n+1];
a[1]=0;a[2]=12;
for(int i=3;i<=(max-7);++i) {
a[i]=(2*a[i-1])%max+(3*a[i-2])%max;
a[i]%=max;
}
return a[n];
}
int main() {
ios::sync_with_stdio(false);
int t,n;
cin>>t;
while(t--) {
cin>>n;
cout<<schemes(n)<<endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojZGVmaW5lIG1heCAxMDAwMDAwMDA3CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgc2NoZW1lcyhpbnQgbikgewoJaW50IGFbbisxXTsKCWFbMV09MDthWzJdPTEyOwoJZm9yKGludCBpPTM7aTw9KG1heC03KTsrK2kpIHsKCQlhW2ldPSgyKmFbaS0xXSklbWF4KygzKmFbaS0yXSklbWF4OwoJCWFbaV0lPW1heDsKCX0KCXJldHVybiBhW25dOwp9CgppbnQgbWFpbigpIHsKCWlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCWludCB0LG47CgljaW4+PnQ7Cgl3aGlsZSh0LS0pIHsKCQljaW4+Pm47CgkJY291dDw8c2NoZW1lcyhuKTw8ZW5kbDsKCX0KCXJldHVybiAwOwp9