#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;

const int mod=1e9+7;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}


inline char gc() { // like getchar()
	static char buf[1 << 16];
	static size_t bc, be;
	if (bc >= be) {
		buf[0] = 0, bc = 0;
		be = fread(buf, 1, sizeof(buf), stdin);
	}
	return buf[bc++]; // returns 0 on EOF
}
ll readInt() {
	ll a, c;
	while ((a = gc()) < 40);
	if (a == '-') return -readInt();
	while ((c = gc()) >= 48) a = a * 10 + c - 480;
	return a - 48;
}


ll rr[20];
struct polyn{

    vector<int>a;

    polyn(){}
    polyn(vector<int>b){a=b;}

    void push_back(int x){
        a.pb(x);
    }
    int size(){return a.size();}
    void resize(int n){a.resize(n);}

    int& operator [](int x){
        if(x>=a.size())a.resize(x+1);
        return a[x];
    }

    polyn operator -(polyn b){
        polyn ret;
        ret.resize(max(b.size(),(int)a.size()));
        for(int i=0;i<a.size();i++)ret[i]=add(ret[i],a[i]);
        for(int i=0;i<b.size();i++)ret[i]=sub(ret[i],b[i]);
        return ret;
    }

    polyn operator +(polyn b){
        polyn ret;
        ret.resize(max(b.size(),(int)a.size()));
        for(int i=0;i<a.size();i++)ret[i]=add(ret[i],a[i]);
        for(int i=0;i<b.size();i++)ret[i]=add(ret[i],b[i]);
        return ret;
    }

    polyn operator *(int c){
        polyn ret=(*this);
        for(int i=0;i<ret.size();i++)ret[i]=mul(ret[i],c);
        return ret;
    }

    friend polyn operator *(const int c,polyn p){
        return p*c;
    }

    polyn brute_pmul(polyn b){
        polyn ret;
        ret.resize(a.size()+b.size()-1);
        for(int i=0;i<a.size()+b.size()-1;i++)rr[i]=0;

        for(int i=0;i<a.size();i++)
            for(int j=0;j<b.size();j++)
                rr[i+j]+=(ll)a[i]*b[j];

        for(int i=0;i<a.size()+b.size()-1;i++)ret[i]=rr[i]%mod;
        return ret;
    }

    polyn operator *(polyn b){
        return brute_pmul(b);
    }

    void ispis(){
        for(int i=0;i<a.size();i++)printf("%d ",a[i]);
        printf(" ISPIS\n");
    }

};

int get_fp(polyn P,polyn Q){
    return P.size()*Q.size()+Q.size()*Q.size();
}

polyn FGP,FGQ,PP,QQ,PP2,QQ2;
void init(){

    polyn pom;
    pom[0]=1;
    pom[2]=mod-1;

    polyn P=pom;

    ///P.ispis();

    polyn x;
    x[1]=1;

    polyn Q=P*P-x+x*P;


    polyn P2=P*x+Q*pom;
    polyn Q2=Q*pom;

    //P.ispis();
    //FGP=P;
    //FGQ=Q;

    FGP=P*Q2+P2*Q;
    FGQ=Q*Q2;

    PP=P;
    QQ=Q;
    PP2=P2;
    QQ2=Q2;

    /*printf("%d %d | %d %d | %d %d AA\n",P.size(),Q.size(),P2.size(),Q2.size(),FGP.size(),FGQ.size());


    int pom1=60*(get_fp(P,Q)+get_fp(P2,Q2));
    int pom2=60*(get_fp(FGP,FGQ));
    printf("%d %d\n",pom1*10000,pom2*10000);*/

    //FGP.ispis();
    //FGQ.ispis();

}

polyn minp(polyn q){
    for(int i=1;i<q.size();i+=2)q[i]=sub(0,q[i]);
    return q;
}
polyn section(polyn p,int f){
    polyn ret;
    for(int i=f;i<p.size();i+=2)ret.push_back(p[i]);
    return ret;
}
int get_rez(ll n,polyn P,polyn Q){

    ///printf("%d %d START\n",P.size(),Q.size());
    while(n){

        ///printf("%d %d SZ\n",P.size(),Q.size());

        polyn pomP=section(P*minp(Q),n%2);
        polyn T=section(Q*minp(Q),0);

        P=pomP;
        Q=T;

        n/=2;

    }

    return mul(P[0],invv(Q[0]));
}


int main(){

    //cin.tie(0);
    //ios_base::sync_with_stdio(0);


    freopen("penguin.in","r",stdin);
    freopen("penguin.out","w",stdout);

    init();
    //return 0;

    ll t=readInt();


    while(t--){
        ll n=readInt();
        printf("%d\n",add(get_rez(n,PP,QQ),get_rez(n,PP2,QQ2)) );
    }


    return 0;
}