/*
 * b.cpp 2023-09-30
 * Copyright (C) 2023 Woshiluo Luo <[email protected]>
 *
 * 「Two roads diverged in a wood,and I—
 * I took the one less traveled by,
 * And that has made all the difference.」
 *
 * Distributed under terms of the GNU GNU AGPLv3+ license.
 */
 
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cstring>
 
#include <map>
#include <array>
#include <queue>
#include <vector>
#include <random>
#include <algorithm>
 
typedef const int cint;
typedef long long ll;
typedef unsigned long long ull;
 
inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/
template <class T> 
T Max( T a, T b ) { return a > b? a: b; }
template <class T> 
T Min( T a, T b ) { return a < b? a: b; }
template <class T> 
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T> 
void chk_Min( T &a, T b ) { if( b < a ) a = b; }
template <typename T>
T read() { 
	T sum = 0, fl = 1; 
	char ch = getchar();
	for (; isdigit(ch) == 0; ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}
template <class T> 
T pow( T a, int p ) {
	T res = 1;
	while( p ) {
		if( p & 1 ) 
			res = res * a;
		a = a * a;
		p >>= 1;
	}
	return res;
}/*}}}*/

const int mod = 1e9 + 7;

struct ModInt {/*{{{*/
	int cur;
	ModInt( ll _cur = 0 ) { cur = ( ( ( _cur % mod ) + mod ) % mod ); }

	inline ModInt operator+ ( const ModInt &b ) const { return ( cur + b.cur ) % mod; }
	inline ModInt operator- ( const ModInt &b ) const { return ( ( ( cur - b.cur ) % mod ) + mod ) % mod; }
	inline ModInt operator* ( const ModInt &b ) const { return ( 1LL * cur * b.cur ) % mod; }
	inline ModInt operator/ ( const ModInt &b ) const { return ( 1LL * cur * pow( b, mod - 2 ).cur ) % mod; }

	inline void operator+= ( const ModInt &b ) { (*this) = (*this) + b; }
	inline void operator-= ( const ModInt &b ) { (*this) = (*this) - b; }
	inline void operator*= ( const ModInt &b ) { (*this) = (*this) * b; }
	inline void operator/= ( const ModInt &b ) { (*this) = (*this) / b; }

	inline void output( const char end = '\n' ) { printf( "%d%c", cur, end ); }
};/*}}}*/

const int32_t P = 1 << 9;


int32_t hash( const int32_t x, const int32_t y ) {
	return ( 2 - y ) * 3 + x;
}
int32_t full_pow( const int32_t cur ) {
	return 1 << cur;
}
int32_t set_bit( const int32_t cur, const int32_t pos ) {
	return cur | full_pow(pos);
}
bool chk_pos( const int32_t cur, const int32_t pos ) {
	return ( cur >> pos ) & 1;
}

ModInt f[P], g[P][32];

const int LP = 1 << 6;
struct Matrix {/*{{{*/
	ModInt a[LP][LP];
	Matrix( const int cur = 0 ) {
		if( cur ) 
			for( int i = 0; i < LP; i ++ ) 
				a[i][i] = 1;
	}
	Matrix operator* ( const Matrix &_b ) const {
		Matrix res;
		for( int i = 0; i < LP; i ++ ) {
			for( int j = 0; j < LP; j ++ ) {
				for( int k = 0; k < LP; k ++ ) {
					res.a[i][j] += a[i][k] * _b.a[k][j];
				}
			}
		}
		return res;
	}
	void operator*= ( const Matrix &_b ) { (*this) = (*this) * _b; }
} p;/*}}}*/

struct Node { int32_t x, y; };
Node block[][3] = { 
	{ { 0, 0 }, { 0, 1 }, { 0, 2 } },
	{ { 0, 0 }, { 1, 0 }, { 2, 0 } },
	{ { 0, 0 }, { 0, 1 }, { 1, 0 } },
	{ { 0, 0 }, { 0, 1 }, { 1, 1 } },
	{ { 0, 0 }, { 1, 0 }, { 1, 1 } },
	{ { 0, 1 }, { 1, 0 }, { 1, 1 } },
};

int main() {
#ifdef woshiluo
	freopen( "l.in", "r", stdin );
	freopen( "l.out", "w", stdout );
#endif
	std::vector<uint32_t> blocks;
	{/*{{{*/
		auto chk = [] ( const int32_t cur, const int32_t left, const int32_t rig ) {
			return ( cur >= left ) && ( cur < rig );
		};
		for( auto p: block ) {
			for( int i = 0; i < 3; i ++ ) {
				for( int j = 0; j < 3; j ++ ) {
					int mask = 0;
					bool flag = true;
					for( int k = 0; k < 3; k ++ ) {
						const auto node = p[k];
						if( chk( node.x + i, 0, 3 ) && chk( node.y + j, 0, 3 ) ) {
							mask = set_bit( mask, hash( node.x + i, node.y + j ) );
							continue;
						}
						flag = false;
						break;
					}
					if( !flag ) 
						continue;
					blocks.push_back(mask);
				}
			}
		}
	}/*}}}*/

	{/*{{{*/
		const int32_t size = blocks.size();
		for( int j = 0; j < size; j ++ ) 
			g[ blocks[j] ][j] = 1;
		for( int j = 0; j < size; j ++ ) {
			for( int i = 0; i < P; i ++ ) {/*{{{*/
				for( int k = j + 1; k < size; k ++ ) {
					const int mask = blocks[k];
					if( i & mask ) 
						continue;
					g[ i | mask ][k] += g[i][j];
				}
			}
		}/*}}}*/
		for( int i = 0; i < P; i ++ ) {
			for( int j = 0; j < size; j ++ ) 
				f[i] += g[i][j];
		}
		f[0] = 1;
	}/*}}}*/


	for( int i = 0; i < full_pow(6); i ++ ) {
		for( int j = 0; j < full_pow(6); j ++ ) {
			if( ( ( j >> 3 ) & 7 ) < ( i & 7 ) )
				continue;
			const int32_t mask = ( ( 7 ^ ( i >> 3 ) ) << 6 ) |
				( ( ( ( j >> 3 ) & 7 ) ^ ( i & 7 ) ) << 3 ) |
				( ( j & 7 ) );
			if( ( j & 7 ) == 0 )
				continue;
			p.a[i][j] += f[mask];
#ifdef woshiluo
			printf( "mask(%5d, %5d) = %d\n", i, j, mask );
#endif
		}
	}

#ifdef woshiluo
	for( int i = 0; i < full_pow(6); i ++ ) {
		for( int j = 0; j < full_pow(6); j ++ ) {
			printf( "(%5d, %5d) = %5d\n", i, j, p.a[i][j] );
		}
	}
#endif

	int T = read<int>();
	while( T -- ) {
		cint n = read<ll>();
		if( n <= 2 ) {
			if( n == 1 ) 
				printf( "1\n" );
			if( n == 2 ) 
				printf( "3\n" );
			if( n == 3 ) 
				printf( "10\n" );
			continue;
		}
		Matrix a;
		a.a[0][0] = 1;
		a *= pow( p, n - 2 );
		a.a[0][63].output();
	}
}