简单的不能再简单了……
//母函数为G(x) = [ e^(4x) + 2*e^(2x) + 1 ]/4
//易见x^n项的系数为: ( 4^n + 2^(n+1) )/4 = 4^(n-1) + 2^(n-1)
#include <stdio.h>
#define MOD 10007	//已计算过不会发生越界错误

int main(){
	int t,n,a,ans;
	scanf("%d", &t);
	while (t--){
		scanf("%d", &n);
		n = (n-1)%(MOD-1);	//此处应用费马小定理
		ans=1,a=2;
		while (n){	//计算2^n
			if (n&1)		ans = (ans*a)%MOD;
			a = (a*a)%MOD;
			n>>=1;
		}
		ans = ( ans + ans*ans ) % MOD;
		printf("%d\n", ans);
	}
	return 0;
}