#include <cstdio>
#include <queue>
using namespace std;

const int mod=1e9+7;
int modex(int b, int e){
	int h = 1;
	while(e){
		if(e&1)
			h=(long long)h*b %mod;
		b=(long long)b*b %mod;
		e>>=1;
	}
	return h;
}
int invs(int x){
	return modex(x, mod-2);
}
const int coefsEven[]={
	1024, 9984, 44032, 115920, 202380, 246047, 212681, 130923, 56485, 16445, 3003, 297, 11, 0, 0, 0
};
const int coefsOdd[]={
	1024, 10496, 48896, 136752, 255420, 335137, 316184, 215644, 105248, 35750, 8008, 1068, 68, 1, 0, 0
};
int main(){
	int t=1;
	scanf("%d", &t);
	while(t--){
		int n;
		scanf("%d", &n);
		if(n&1){
			n/=2;n++;
			long long ans=coefsOdd[0];
			for(int i = 1;i < 16;i ++){
				ans=ans*(n-16+i) %mod *invs(16-i) %mod;
				ans+=coefsOdd[i];
			}
			printf("%lld\n", ans);
		}else{
			n/=2;n++;
			long long ans=coefsEven[0];
			for(int i = 1;i < 16;i ++){
				ans=ans*(n-16+i) %mod *invs(16-i) %mod;
				ans+=coefsEven[i];
			}
			printf("%lld\n", ans);
		}
	}
}