#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_stdin ( false ) ;
int t,n;
cin >> t;
while ( t-- ) {
cin >> n;
cout << schemes( n) << endl;
}
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojZGVmaW5lIG1heCAxMDAwMDAwMDA3CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgc2NoZW1lcyhpbnQgbikgewoJaW50IGFbbisxXTsKCWFbMV09MDthWzJdPTEyOwoJZm9yKGludCBpPTM7aTw9KG1heC03KTsrK2kpIHsKCQlhW2ldPSgyKmFbaS0xXSklbWF4KygzKmFbaS0yXSklbWF4OwoJCWFbaV0lPW1heDsKCX0KCXJldHVybiBhW25dOwp9CgppbnQgbWFpbigpIHsKCWlvczo6c3luY193aXRoX3N0ZGluKGZhbHNlKTsKCWludCB0LG47CgljaW4+PnQ7Cgl3aGlsZSh0LS0pIHsKCQljaW4+Pm47CgkJY291dDw8c2NoZW1lcyhuKTw8ZW5kbDsKCX0KCXJldHVybiAwOwp9