#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const long long MOD=1000000007;
const long double Pi=acos(-1);
using P=pair<ll,ll>;
ll gcd(ll a,ll b){//aとbの最大公約数を返す//計算量は0(log(max(a,b))
  if(a%b==0){return b;}
  else{return gcd(b,a%b);}
}
ll lcm(ll a,ll b){//aとbの最小公倍数を返す//計算量は0(log(max(a,b))
  return a*b/gcd(a,b);
}
ll mod_pow(ll x,ll y){//x^yを返す//計算量は0(log(y))
  ll tmp=x,res=1;
  while(y){
    if(y%2){res=res*tmp%MOD;}
    y>>=1;
    tmp=tmp*tmp%MOD;
  }
  return res;
}
ll nature(ll a){//絶対値を返す
  if(a>=0){return(a);}
  else{return(-1*a);}
}
ll prime(ll a){//素数なら1を返す//計算量は0(sqrt(a))
  if(a==2){return 1;}
  else if(a%2==0 || a==1){return 0;}
  for(ll i=3;i*i<=a;i+=2){if(a%i==0){return 0;}}
  return 1;
}
vector<long long> Z;
void z_algorithm(string str){//計算量はO(str.size())
  Z.resize(str.size());
  Z.at(0)=str.size();
  long long m=1,n=0;
  while(m<(long long)str.size()){
    while(m+n<(long long)str.size()&&str.at(n)==str.at(m+n)){n++;}
    Z.at(m)=n;
    if(n==0){
      m++;
      continue;
    }
    long long k=1;
    while(k+Z.at(k)<n){
      Z.at(m+k)=Z.at(k);
      k++;
    }
    m+=k;
    n-=k;
  }
}
template <typename T>
struct BIT{
    //区間加算O(log(N))
    //区間シグマ計算O(log(N))
    //単点加算O(log(N))
    //単点計算O(log(N))
    long long n;//元の数列のサイズ
    vector<T> bit[2];//データ収納用
    vector<T> for_bubblesort;
    void init(long long n_){
        n=n_+1;
        for(long long j=0;j<2;j++){
            bit[j].assign(n,0);
        }
    }
    void add_sub(long long p,long long i,T x){
        for(long long j=i;j<n;j+=j&-j){
            bit[p][j]+=x;
        }
    }
    void add(long long l,long long r,T x){//[l,r]に加算
        add_sub(0,l,-x*(l-1));
        add_sub(0,r+1,x*r);
        add_sub(1,l,x);
        add_sub(1,r+1,-x);
    }
    T sum_sub(long long p,long long i){
        T s(0);
        for (long long j=i;j>0;j-=j&-j){
            s+=bit[p][j];
        }
        return s;
    }
    T sum(long long i,long long j){//[i,j]のΣを計算
        return sum_sub(0,j)+sum_sub(1,j)*j-sum_sub(0,i-1)-sum_sub(1,i-1)*(i-1);
    }
    //ここから二分探索関連
    T binary_search_sum1(long long key){//a_1+a_2+...+a_x>=keyとなるような最小のxを求める(ただしa_i>=0)
    //key以上の値
            if(key<=0){
                return 0;
            }
            else{
                long long x=0,r=1;
                while(r<n){
                    r=r<<1;
                }
                for(long long length=r;length>0;length=length>>1){//長さlenは1段下るごとに半分に
                    if(x+length<n&&sum(x+1,x+length)<key){//採用するとき
                        key-=sum(x+1,x+length);
                        x+=length;
                    }
                }
                return x+1;
            }
    }
    T binary_search_sum2(long long key){//a_1+a_2+...+a_x<=keyとなるような最大のxを求める(ただしa_i>=0)
    //key以下の値
            key++;
            if(key<=0){
                return 0;
            }
            else{
                long long x=0,r=1;
                while(r<n){
                    r=r<<1;
                }
                for(long long length=r;length>0;length=length>>1){//長さlenは1段下るごとに半分に
                    if(x+length<n&&sum(x+1,x+length)<key){//採用するとき
                        key-=sum(x+1,x+length);
                        x+=length;
                    }
                }
                return x;
            }
    }
    //二分探索終わり
    //ここからはbubblesort関連
    void init_bubblesort(long long n_){
        n=n_+1;
        for_bubblesort.assign(n,0);
    }
    void add_bubblesort(long long i,T x) {
        for(long long j=i;j<n;j+=j&-j){
            for_bubblesort[j]+=x;
        }
    }
    T calculate_bubblesort(long long i) {
        T s=0;
        for(long long j=i;j>0;j-=j&-j){
            s+=for_bubblesort[j];
        }
        for(long long j=i-1;j>0;j-=j&-j){
            s-=for_bubblesort[j];
        }
        return s;
    }
    T bubblesort(){
        //bitとfor_bubblesort両方initしてadd_for_bubblesortしてから使う
        long long answer_for_bubblesort=0;
        long long sum_for_bubblesort;
        for(long long i=1;i<=n-1;i++){
            sum_for_bubblesort=calculate_bubblesort(i);
            answer_for_bubblesort+=i-sum(1,sum_for_bubblesort)-1;
            add(sum_for_bubblesort,sum_for_bubblesort,1);
        }
        return answer_for_bubblesort;
    }
    //bubblesort関連終わり
    /*
    使い方
    BIT<long long> rock;
    rock.init(N);    Nは加算などの操作を行う配列のサイズ
    ...(その後は適当に)
    */
};
template<typename T>
struct BIT2D{
    //単点に値たすO(1)
    //[1,h][1,w]の総和O(log(h)*log(w))
    //[h,hh][w,ww]の値の総和O(4*log(max(h,w,hh,ww)))
    long long H,W;
    vector<vector<T>> bit;
    void init(long long H_,long long W_){
        H=H_+1;
        W=W_+1;
        bit.assign(H,vector<T>(W,0));
    }
    void add(long long h,long long w,T x){//(h,w)にxを足す0(log(h)*log(w))  (区間サイズnの場合O(N))
        for(long long i=h;i<H;i+=i&-i){
            for(long long j=w;j<W;j+=j&-j){
                bit[i][j]+=x;
            }
        }
    }
    T sum(long long h,long long w){//[1,h][1,w]の総和O(log(h)*log(w))
        T s=0;
        for(long long i=h;i>0;i-=i&-i){
            for(long long j=w;j>0;j-=j&-j){
                s+=bit[i][j];
            }
        }
        return s;
    }
    T partsum(long long h,long long w,long long hh,long long ww){//[h,hh][w,ww]の総和O(log(max(h,w,hh,ww)))
        //前処理でsumを計算しておけば計算量減らせるかも
        return sum(hh,ww)+sum(h-1,w-1)-sum(hh,w-1)-sum(h-1,ww);
    }
};
template<typename T>
struct Fiduccia{
    //Qの定数項の方が大きい場合はできないので注意！！！！！　
    /*
    [x^N]P(x)/Q(x)を求める
    */
    long long PP,QQ;
    vector<T> P;
    vector<T> Q;
    vector<T> Pcopy;
    vector<T> Qcopy;
    vector<T> R;
    vector<T> RR;
    void init(long long PP_,long long QQ_){//最高次
        PP=PP_+1;
        QQ=QQ_+1;
        P.assign(PP+QQ,0);
        Q.assign(PP+QQ,0);
        R.assign(PP+QQ,0);
        RR.assign(PP+QQ,0);
    }
    void consist(char S,long long a,long long b){
        /*
        ax^bの計算
        0乗も忘れずに
        */
        if(S=='P'){
            P.at(b)=a;
        }
        else{
            Q.at(b)=a;
        }
    }
    void calculate_init(long long N){
        /*
        n乗の係数を求める。
        */
        while(N>0){
            /*
            P(x)とQ(-x)の積をまず計算(R(x))で表す
            偶数乗項の係数のみを順番に集めていく
            */
            for(long long i=0;i<PP;i++){
                for(long long j=0;j<QQ;j++){
                    long long a;
                    if(j%2==0){
                        a=P.at(i)*Q.at(j);
                    }
                    else{
                        a=-1*P.at(i)*Q.at(j);
                    }
                    if((i+j)%2==0){
                        R.at((i+j)/2)+=a;
                    }
                }
            }
            for(long long i=0;i<PP;i++){
                for(long long j=0;j<QQ;j++){
                    long long a;
                    if(j%2==0){
                        a=P.at(i)*Q.at(j);
                    }
                    else{
                        a=-1*P.at(i)*Q.at(j);
                    }
                    if((i+j)%2==1){
                        RR.at((i+j)/2)+=a;
                    }
                }
            }
            /*
            R(x)とRR(x)で表すのは終わり
            */
            if(N%2==0){
                N/=2;
                for(long long i=0;2*i<PP+QQ;i++){
                    P.at(i)=R.at(i);
                }
                Qcopy=Q;
                for(long long i=0;i<QQ;i++){
                    Q.at(i)=0;
                }
                for(long long i=0;i<QQ;i++){
                    for(long long j=0;j<QQ;j++){
                        if((i+j)%2==0 && j%2==0){
                            //cout<<i<<" "<<j<<endl;
                            Q.at((i+j)/2)+=Qcopy.at(i)*Qcopy.at(j);
                        }
                        if((i+j)%2==0 && j%2==1){
                            //cout<<i<<" "<<j<<endl;
                            Q.at((i+j)/2)+=-1*Qcopy.at(i)*Qcopy.at(j);
                        }
                    }
                }
            }
            else{
                N--;
                N/=2;
                for(long long i=0;2*i<PP+QQ;i++){
                    P.at(i)=RR.at(i);
                }
                Qcopy=Q;
                for(long long i=0;i<QQ;i++){
                    Q.at(i)=0;
                }
                for(long long i=0;i<QQ;i++){
                    for(long long j=0;j<QQ;j++){
                        if((i+j)%2==0 && j%2==0){
                            //cout<<i<<" "<<j<<endl;
                            Q.at((i+j)/2)+=Qcopy.at(i)*Qcopy.at(j);
                        }
                        if((i+j)%2==0 && j%2==1){
                            //cout<<i<<" "<<j<<endl;
                            Q.at((i+j)/2)+=-1*Qcopy.at(i)*Qcopy.at(j);
                        }
                    }
                }
            }
            for(long long i=0;i<(long long)R.size();i++){
                R.at(i)=0;
                RR.at(i)=0;
            }
        }
    }
    T calculate(){//N=0の時を考える//Qの定数項の方が大きい場合はできないので注意
        long long a=P.at(0);
        long long b=Q.at(0);
        return a/b;
    }
};
template<typename T>
struct Fiduccia_MOD{
    //Qの定数項の方が大きい場合はできないので注意！！！！！　
    /*
    [x^N]P(x)/Q(x)を求める
    */
    long long PP,QQ,Tmod=1000000007;
    vector<T> P;
    vector<T> Q;
    vector<T> Pcopy;
    vector<T> Qcopy;
    vector<T> R;
    vector<T> RR;
    void init(long long PP_,long long QQ_){//最高次
        PP=PP_+1;
        QQ=QQ_+1;
        P.assign(PP+QQ,0);
        Q.assign(PP+QQ,0);
        R.assign(PP+QQ,0);
        RR.assign(PP+QQ,0);
    }
    void consist(char S,long long a,long long b){
        /*
        ax^bの計算
        0乗も忘れずに
        */
        if(S=='P'){
            P.at(b)=a;
        }
        else{
            Q.at(b)=a;
        }
    }
    void calculate_init(long long N){
        /*
        n乗の係数を求める。
        */
        while(N>0){
            /*
            P(x)とQ(-x)の積をまず計算(R(x))で表す
            偶数乗項の係数のみを順番に集めていく
            */
            for(long long i=0;i<PP;i++){
                for(long long j=0;j<QQ;j++){
                    long long a;
                    if(j%2==0){
                        a=P.at(i)*Q.at(j)%Tmod;
                    }
                    else{
                        a=-1*P.at(i)*Q.at(j)%Tmod;
                    }
                    if((i+j)%2==0){
                        R.at((i+j)/2)+=a;
                        R.at((i+j)/2)%=Tmod;
                    }
                }
            }
            for(long long i=0;i<PP;i++){
                for(long long j=0;j<QQ;j++){
                    long long a;
                    if(j%2==0){
                        a=P.at(i)*Q.at(j)%Tmod;
                    }
                    else{
                        a=-1*P.at(i)*Q.at(j)%Tmod;
                    }
                    if((i+j)%2==1){
                        RR.at((i+j)/2)+=Tmod+a;
                        RR.at((i+j)/2)%=Tmod;
                    }
                }
            }
            /*
            R(x)とRR(x)で表すのは終わり
            */
            if(N%2==0){
                N/=2;
                for(long long i=0;2*i<PP+QQ;i++){
                    P.at(i)=R.at(i);
                }
                Qcopy=Q;
                for(long long i=0;i<QQ;i++){
                    Q.at(i)=0;
                }
                for(long long i=0;i<QQ;i++){
                    for(long long j=0;j<QQ;j++){
                        if((i+j)%2==0 && j%2==0){
                            //cout<<i<<" "<<j<<endl;
                            Q.at((i+j)/2)+=Tmod+Qcopy.at(i)*Qcopy.at(j);
                            Q.at((i+j)/2)%=Tmod;
                        }
                        if((i+j)%2==0 && j%2==1){
                            //cout<<i<<" "<<j<<endl;
                            Q.at((i+j)/2)+=Tmod-1*Qcopy.at(i)*Qcopy.at(j);
                            Q.at((i+j)/2)%=Tmod;
                        }
                    }
                }
            }
            else{
                N--;
                N/=2;
                for(long long i=0;2*i<PP+QQ;i++){
                    P.at(i)=RR.at(i);
                }
                Qcopy=Q;
                for(long long i=0;i<QQ;i++){
                    Q.at(i)=0;
                }
                for(long long i=0;i<QQ;i++){
                    for(long long j=0;j<QQ;j++){
                        if((i+j)%2==0 && j%2==0){
                            //cout<<i<<" "<<j<<endl;
                            Q.at((i+j)/2)+=Qcopy.at(i)*Qcopy.at(j);
                            Q.at((i+j)/2)%=Tmod;
                        }
                        if((i+j)%2==0 && j%2==1){
                            //cout<<i<<" "<<j<<endl;
                            Q.at((i+j)/2)+=-1*Qcopy.at(i)*Qcopy.at(j);
                            Q.at((i+j)/2)%=Tmod;
                        }
                    }
                }
            }
            for(long long i=0;i<(long long)R.size();i++){
                R.at(i)=0;
                RR.at(i)=0;
            }
        }
    }
    T calculate(){//N=0の時を考える//Qの定数項の方が大きい場合はできないので注意
        long long a=P.at(0);
        long long b=Q.at(0);
        return a/b;
    }
};
int main(){
  long long T;
  cin>>T;
  for(long long e=0;e<T;e++){
  long long N;
  cin>>N;
  N-=5;
  if(N<0){cout<<0<<endl;continue;}
  Fiduccia_MOD<long long> rock;
  rock.init(21,21);//max最高次にする
  rock.consist('P',1,0);
  rock.consist('Q',1,0);
  rock.consist('Q',-11,1);
  rock.consist('Q',50,2);
  rock.consist('Q',-110,3);
  rock.consist('Q',65,4);
  rock.consist('Q',253,5);
  rock.consist('Q',-648,6);
  rock.consist('Q',440,7);
  rock.consist('Q',610,8);
  rock.consist('Q',-1430,9);
  rock.consist('Q',780,10);
  rock.consist('Q',780,11);
  rock.consist('Q',-1430,12);
  rock.consist('Q',610,13);
  rock.consist('Q',440,14);
  rock.consist('Q',-648,15);
  rock.consist('Q',253,16);
  rock.consist('Q',65,17);
  rock.consist('Q',-110,18);
  rock.consist('Q',50,19);
  rock.consist('Q',-11,20);
  rock.consist('Q',1,21);
  rock.calculate_init(N);
  cout<<rock.calculate()<<endl;
  }
}

Measured memory_bytes: 3616