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