#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>
using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back

ll mod;

ll one(){
    ll a = (ll)true;
    return a;
}
ll two(){
    ll a = (ll)true;
    a++;
    return a;
}
ll three(){
    ll a = (ll)true;
    a++;
    a++;
    return a;
}
ll seven(){
    ll a = three();
    a++;
    a++;
    a++;
    a++;
    return a;
}
ll nine(){
    return two()+seven();
}
ll ten(){
    ll a = nine();
    a++;
    return a;
}

ll zero(){
    ll a = one();
    a--;
    return a;
}


ll divide(ll a,ll b){
    lldiv_t c = div(a,b);
    return c.quot;
}
ll modulo(ll a,ll b){
    lldiv_t c = div(a,b);
    return c.rem;
}

ll mul(ll a,ll b){
    if(b==zero())return zero();
    if(b==one())return a;
    if(modulo(b,two())==zero()){
        ll c = mul(a,divide(b,two()));
        return modulo(c+c,mod);
    }else{
        ll c = mul(a,divide(b,two()));
        return modulo(c+c+a,mod);
    }
}

ll mult(ll a,ll b){
    if(b==zero())return zero();
    if(b==one())return a;
    if(modulo(b,two())==zero()){
        ll c = mult(a,divide(b,two()));
        return c+c;
    }else{
        ll c = mult(a,divide(b,two()));
        return c+c+a;
    }
}
void mod_calc(){
    mod = one();
    for(int i=zero();i<nine();i++){
        mod = mult(mod,ten());
    }
    mod += seven();
    return;
}

vector<vector<ll> > mat_mul(vector<vector<ll> > &v,vector<vector<ll> > &w){
    vector<vector<ll> > z(two(),vector<ll>(two()));
    z[zero()][zero()] = modulo(mul(v[zero()][zero()],w[zero()][zero()])+mul(v[zero()][one()],w[one()][zero()]),mod);
    z[zero()][one()] = modulo(mul(v[zero()][zero()],w[zero()][one()])+mul(v[zero()][one()],w[one()][one()]),mod);
    z[one()][zero()] = modulo(mul(v[one()][zero()],w[zero()][zero()])+mul(v[one()][one()],w[one()][zero()]),mod);
    z[one()][one()] = modulo(mul(v[one()][zero()],w[zero()][one()])+mul(v[one()][one()],w[one()][one()]),mod);
    return z;
}

vector<vector<ll> > mat_calc(vector<vector<ll> > &v,ll n){
    if(n==zero()){
        vector<vector<ll> > z(two(),vector<ll>(two()));
        z[zero()][zero()]=one();
        z[one()][one()]=one();
        return z;
    }
    if(n==one())return v;
    if(modulo(n,two())==zero()){
        vector<vector<ll> > z(two(),vector<ll>(two()));
        z = mat_calc(v,divide(n,two()));
        return mat_mul(z,z);
    }else{
        vector<vector<ll> > z(two(),vector<ll>(two()));
        z = mat_calc(v,divide(n,two()));
        z = mat_mul(z,z);
        return mat_mul(z,v);
    }
}

ll calc(ll n){
    vector<vector<ll> > v(two(),vector<ll>(two()));
    v[zero()][zero()] = zero();
    v[zero()][one()] = one();
    v[one()][zero()] = one();
    v[one()][one()] = one();
    vector<vector<ll> > z(two(),vector<ll>(two()));
    z = mat_calc(v,n);
    
    return modulo(mul(z[zero()][zero()],two())+mul(z[zero()][one()],one()),mod);
}

int main(){
    mod_calc();
    int t;
    cin >> t;
    for(int i=zero();i<t;i++){
        ll n;
        cin >> n;
        cout << calc(n) << endl;
    }
    return zero();
}