#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<cmath>
#include<cstring>
#include<set>
#include<climits>
#include<deque>
#include <iomanip>
#include<utility>
using namespace std;

#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define all(a) a.begin(),a.end()
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define size(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
#define S 21 
llfor;
const int mod=1e9+7;
/*pi*/double pi=acos(-1);
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll ans=1;rep(i,0,n){ans*=x;ans%=mod;}return ans;}
/*階乗*/ll fact(ll x){ll ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)*fact(n-r)/fact(r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
/*Fibonacci数列*/ll fib(ll x){ll fibo[x+10];fibo[0]=1;fibo[1]=1;fibo[2]=1;rep(i,3,x+1)fibo[i]=fibo[i-1]+fibo[i-2];return fibo[x];}
/*桁数*/ll dig(ll n){ll d=1,tmp=n;while(tmp/10>0){tmp/=10;d++;}return d;}
/*行列のコピー*/void matcpy(ll a[S][S],ll b[S][S]){ll t=i;rep(i,0,S)rep(j,0,S)b[i][j]=a[i][j];/*(aをbに)*/i=t;}
/*行列のリセット*/void matrst(ll a[S][S]){ll t=i;rep(i,0,S)rep(j,0,S)a[i][j]=0;i=t;}
/*行列の2乗*/void matpow(ll a[S][S]){ll ans[S][S];matrst(ans);ll t=i,k;rep(i,0,S)rep(j,0,S)rep(k,0,S){ans[i][j]+=a[i][k]*a[k][j];ans[i][j]%=mod;}matcpy(ans,a);i=t;}
/*行列の乗算*/void matmul(ll a[S][S],ll b[S][S], ll as[S][S]){ll t=i,k;matrst(as);rep(i,0,S)rep(j,0,S)rep(k,0,S){as[i][j]+=a[i][k]*b[k][j];as[i][j]%=mod;}i=t;}
//ll ans=0;
////////////////////////////////////////////////////////////
int main(){
 ll t;
 cin>>t;
 ll a,ans;
 ll s,n,u,k,e;

 //累乗するベースの行列
 ll base[S][S];
 rep(i,0,S){
  rep(j,0,S){
   if(i<10){
    if(i%2==0&&(j==i+1||j==i-2))base[i][j]=1;
    else if(i%2==1&&j==i-1)base[i][j]=1;
    else base[i][j]=0;
   }
   else if(i==10){
    if(j==i||j==i-2)base[i][j]=1;
   }
   else if(j==i||j==i-1)base[i][j]=1;    
   else base[i][j]=0;  
  }
 } 
  /*
  rep(n,0,S){
   rep(u,0,S){
    cout<<base[n][u]<<" ";
   }
   pnn;
  }
  */
 //最後にかける行列
 ll last[S][S]; 
 rep(i,0,S){
  rep(j,0,S){
   if(i==0&&j==0)last[i][j]=1;
   else last[i][j]=0;
  }
 }
 //ループ
 ll cnt,tmp[S][S],memo[S][S],res,add[S][S];
 rep(s,0,t){
  cin>>a;
  if(a<5){
   puts("0");continue;
  }
  cnt=1;
  matcpy(base,tmp);//tmpはbaseの1乗
  while(cnt*2<a+10){
   matpow(tmp);
   cnt*=2;
 //  cout<<cnt<<" ";
  }
  while(a+10>cnt){
   matcpy(base,add);
   res=1;
   while(res*2<a+10-cnt){
    matpow(add);
    res*=2;
    //cout<<res<<" ";
   }
   matmul(tmp,add,memo);
   matcpy(memo,tmp);
   cnt+=res;
  }
  while(cnt<a+10){
   matmul(tmp,base,memo);
   matcpy(memo,tmp);
   cnt++;
  // cout<<cnt<<" ";
  }
  matmul(tmp,last,memo);
  pr(memo[S-1][0]);
 }
return 0;}

Measured memory_bytes: 3620