题目链接：http://poj.org/problem?id=3734
#include<cstdio>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e4+7;
const int maxn=1e5+4;
const int maxm=1e5+100;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
有四种砖块，铺满n长度
的不同方案数有多少种，
注意：其方案数的计数跟排列有关，
那么就提醒需要用到指数型母函数，
下面说下我对指数型母函数的个人理解：
如果我们直接用一般性的母函数去相乘然后取系数，
得到的就是类似方程解个数这样的方案，答案的贡献仅和大小有关，
对于特定的x1,x2,...xn还要加上：C(n,x1)*x1!*C(n-x1,x2)*x2!...
不难发现这样迭代下去，其系数变成了n!/(x1!*x2!....)，
而指数型母函数把特定物品的展开式本身就附加上系数来构造其最后答案贡献前面的
乘积因子，方法很巧妙~对于这题，偶数只需要把泰勒式子变换下即可，再运算下不难发现其系数就是：4^(n-1)+2^(n-1)。
*/
ll x;
int main(){int t;scanf("%d",&t);while(t--){scanf("%lld",&x);printf("%lld\n",(powmod(4LL,x-1)+powmod(2LL,x-1))%mod);}return 0;
}