#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
 ll MOD=1000000007;
 struct matrix
 {
    ll ar[3][3];
 };
 int n=3;
 const int MD=1e9+7;
 void initializer( matrix &a)
 {
     for(int i=0;i<n;i++)
         for(int k=0;k<n;k++)
            a.ar[i][k]=0;
 }
 matrix MMmult(matrix &a, matrix &b)
 {
     matrix ans;
     initializer(ans);
     for(int i=0;i<n;i++)
         for(int k=0;k<n;k++)
             for(int j=0;j<n;j++)
             {
                 ans.ar[i][k]+=a.ar[i][j]*b.ar[j][k];
                 ans.ar[i][k]%=MD;
             }
     return ans;
 }
 matrix D;
 matrix solve(int x)
 {
     if(x==1)return D;
   matrix ret;
   ret= solve(x/2);
   ret=MMmult(ret,ret);
   if(x%2)ret=MMmult(ret,D);
   return ret;

 }
 int main()
 {
 int t;
 cin>>t;
             initializer(D);
    int bb[3][3]= {{1,2,3},
    {4,5,6 },
       {7,8,9} };
     for(int i=0;i<3;i++)
         for(int k=0;k<3;k++)
             D.ar[i][k]=bb[i][k];
    while(t--)
    {
    int x;
    cin>>x;
    if(x==1)
    {
        cout<<3<<endl;
        continue;
    }   ll sum=0;
         matrix v=solve(x-1);;
        for(int i=0;i<3;i++)

            for(int k=0;k<3;k++)
            {
                sum+=v.ar[i][k];
                sum%=MD;
             }
            cout<<sum<<endl;
    }
     return 0;
 }