#include<bits/stdc++.h>
using namespace std;
//1/(-x^4+2x^3-2x+1)^5
const int mod=1e9+7;
int test,n,p[11],res[22],fuck[22],iv[22],cur,ans;
struct mat
{
	int a[22][22];
	mat()
	{
		for (int i=1;i<=21;i++)
		{
			for (int j=1;j<=21;j++)
			a[i][j]=0;
		}
	}
	mat operator * (const mat &u) const
	{
		mat res;
		for (int i=1;i<=21;i++)
		{
			for (int j=1;j<=21;j++)
			{
				for (int k=1;k<=21;k++)
				{
					res.a[i][j]=(1ll*a[i][k]*u.a[k][j]+res.a[i][j])%mod;
				}
			}
		}
		return res;
	}
}ma,mb;
mat binpow(mat a,int t)
{
	mat res,p=a;
	for (int i=1;i<=21;i++) res.a[i][i]=1;
	for (int i=t;i;i>>=1)
	{
		if (i&1) res=res*p;
		p=p*p;
	}
	return res;
}
int main()
{
	p[0]=1;p[1]=-2;p[3]=2;p[4]=-1;
	res[0]=1;
	for (int i=1;i<=5;i++)
	{
		memset(fuck,0,sizeof(fuck));
		for (int j=(i-1)*4;j>=0;j--)
		{
			for (int k=4;k>=0;k--)
			{
				fuck[j+k]=(1ll*res[j]*p[k]+fuck[j+k])%mod;
			}
		}
		memcpy(res,fuck,sizeof(fuck));
	}
	iv[0]=1;
	for (int i=1;i<=20;i++)
	{
		cur=0;
		for (int j=1;j<=i;j++)
		{
			cur=(-1ll*res[j]*iv[i-j]+cur)%mod;
		}
		iv[i]=cur;
	}
	for (int i=0;i<=20;i++) iv[21]+=iv[i];
	for (int i=1;i<20;i++)
	{
		ma.a[i][i+1]=1;
	}
	for (int i=1;i<=20;i++)
	{
		ma.a[i][1]=-res[i];
		ma.a[i][21]=-res[i];
	}
	ma.a[21][21]=1;
	scanf("%d",&test);
	while(test--)
	{
		scanf("%d",&n);
		if (n<5) printf("0\n");
		else
		{
			n-=5;
			if (n<=20)
			{
				ans=0;
				for (int i=0;i<=n;i++) ans=(ans+iv[i])%mod;
				printf("%d\n",(ans+mod)%mod);
			}
			else 
			{
				mb=binpow(ma,n-20);ans=0;
				for (int i=1;i<=20;i++)
				{
					ans=(1ll*iv[21-i]*mb.a[i][21]+ans)%mod;
				}
				ans=(1ll*iv[21]*mb.a[21][21]+ans)%mod;
				printf("%d\n",(ans+mod)%mod);
			}
		}
	}
	return 0;
}