#include<bits/stdc++.h>

#define ll long long

using namespace std;

const ll Mod=;

inline ll mul(ll x,ll y,ll p){

  return ((x*y-(ll)(((long double)x*y+0.5)/p)*p)%p+p)%p;

}

struct mat

{

    ll M[][];

    mat() { memset(M,,sizeof(M)); }

    mat friend operator *(mat a,mat b)

    {

        mat res;

        for(int k=;k<=;k++)

         for(int i=;i<=;i++)

          for(int j=;j<=;j++)

           res.M[i][j]=(res.M[i][j]+mul(a.M[i][k],b.M[k][j],Mod))%Mod;

        return res;

    }

    mat friend operator ^(mat a,ll x)

    {

       mat res; res.M[][]=res.M[][]=1LL;

       while(x){

          if(x&1LL) res=res*a; a=a*a; x/=;

       } return res;

    }

};

ll qpow(ll a,ll x,ll p){

    ll res=; while(x){

        if(x&1LL) res=mul(res,a,p);

        a=mul(a,a,p); x/=;

    } return res;

}

int main()

{

    int T; ll N,num;

    scanf("%d",&T);

    while(T--){

        scanf("%lld",&N);

        num=qpow(2LL,N,Mod-);

        num--; if(num<) num+=Mod-;

        mat base,a;

        base.M[][]=base.M[][]=base.M[][]=1LL; a.M[][]=1LL;

        base=base^num;

        a=base*a;

        printf("%lld\n",a.M[][]);

    }

    return ;

}