#include<iostream>
#include<vector>
#include<cmath>
#include<numeric>
using namespace std;
typedef long long int ll;
const ll zero=false;
const int one=true;
const int two=one<<one;
const int three=two|one;
const int four=two<<one;
const int five=four|one;
const int six=three<<one;
const int seven=six|one;
const int eight=four<<one;
const int nine=eight|one;
const int ten=five<<one;
ll product(ll A,ll B){vector<ll>a={A},b={B};return inner_product(a.begin(),a.end(),b.begin(),zero);}
ll add(ll A,ll B){vector<ll>v={A,B};return accumulate(v.begin(),v.end(),zero);}
#define FOR(i,l,r) for(ll i=l;i<r;i=add(i,one))
#define REP(i,n) FOR(i,zero,n)
int minu=zero;
const int mod=add(pow(ten,nine),seven);
ll remainder(ll N){
  ll l=zero,r=mod;
  while(r!=add(l,one)){
    ll m=add(l,r)>>one;
    if(product(m,mod)<=N)l=m;
    else r=m;
  }
  N=add(N,product(minu,product(l,mod)));
  while(N>=mod)N=add(N,product(minu,mod));
  return N;
}
vector<vector<ll>>P(vector<vector<ll>>A,vector<vector<ll>>B){
  vector<vector<ll>>res(two,vector<ll>(two));
  REP(i,two)REP(j,two)REP(k,two)res[i][j]=remainder(add(res[i][j],product(A[i][k],B[k][j])));
  return res;
}
int main(){
  int T;cin>>T;
  REP(i,product(four,eight))minu=add(minu,one<<i);
  do{
    int N;cin>>N;
    vector<vector<ll>>A={{one,one},{one,zero}},E={{one,zero},{zero,one}};
    while(N){
      if(N&one)E=P(A,E);
      A=P(A,A);
      N>>=one;
    }
    cout<<remainder(add(E[one][zero],product(two,E[one][one])))<<endl;
  }while(T=add(T,minu));
}