#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <utility>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> ipair;
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz size()
#define ln length()
#define rep(i,n) for(i=0;i<n;i++)
#define fu(i,a,n) for(i=a;i<=n;i++)
#define fd(i,n,a) for(i=n;i>=a;i--)
#define all(a)  a.begin(),a.end()
#define gi(n) scanf("%d",&n)
#define gl(n) scanf("%lld",&n)
#define pi(n) printf("%d",n)
#define pl(n) printf("%lld",n);
#define pp printf(" ")
#define pn printf("\n")
#define LN 31
#define MAX 100005
#define EXP 30
ll expo;
ll mat[EXP][EXP];
void mul(ll a[][EXP], ll b[][EXP], ll ans[][EXP]) {
    ll i, j, k;
    rep(i, expo) {
        rep(j, expo) {
            ans[i][j] = 0;
            rep(k, expo) {
                ans[i][j] = (ans[i][j] + (a[i][k] * b[k][j])%mod)%mod;
            }
        }
    }
}

void copy(ll a[][EXP], ll b[][EXP]) {
    ll i, j;
    rep(i, expo) {
        rep(j, expo) {
            a[i][j] = b[i][j];
        }
    }
}
void calc(ll a[][EXP], ll n, ll ans[][EXP]) {
    ll i, j;
    rep(i, expo) {
        rep(j, expo) {
            if(i == j) {
                ans[i][j] = 1;
            }
            else {
                ans[i][j] = 0;
            }
        }
    }
    if(n == 0) {
        return;
    }
    ll temp[EXP][EXP];
    while(n > 0) {
        if(n&1) {
            mul(ans, a, temp);
            copy(ans, temp);
        }
        mul(a, a, temp);
        copy(a, temp);
        n>>=1;
    }
}

//1->M, 2->W, 3->S

int checkVal(ll val) {
    //cout << val << endl;
    vector<int> v;
    while(val) {
        v.pb(val%10);
        val/=10;
    }
    int c1 = 0;
    int c2 = 0;
    int c3 = 0;
    ll i;
    rep(i, v.size()) {
        if(v[i] == 1) {
            if(i) {
                c2++;
            }
            if(i < 3) {
                c1++;
            }
        }
        else if(v[i] == 3) {
            c3++;
        }
    }
    if(c3 > 2) {
        return 0;
    }
    if(c1 > 1 || c2 > 1) {
        return 0;
    }
    rep(i, v.size() - 1) {
        if(v[i] == 2 && v[i + 1] == 2) {
            return 0;
        }
    }
    //cout << "ok" << endl;
    return 1;
}
int main() {
    vector<ll> v;
    ll i, j, k;
    fu(i, 1, 3) {
        fu(j, 1, 3) {
            fu(k, 1, 3) {
                ll val = i * 100 + j * 10 + k;
                if(checkVal(val)) {
                    v.pb(val);
                    //cout << val << " ";
                }
            }
        }
    }
    //cout << endl;
    expo = v.size();
    rep(i, v.size()) {
        rep(j, v.size()) {
            if(v[i]%100 == v[j]/10) {
                ll val = v[i] * 10 + v[j]%10;
                //cout << val << endl;
                mat[i][j] = checkVal(val);
            }
            else {
                mat[i][j] = 0;
            }
            //cout << mat[i][j] << " ";
        }
        //cout << endl;
    }
    int t;
    gi(t);
    while(t--) {
        ll n;
        gl(n);
        if(!n) {
            pl(n + 1);
            pn;
            continue;
        }
        if(n <= 2) {
            pl(4 * n - 1);
            pn;
        }
        else {
            ll arr[EXP][EXP];
            ll ans[EXP][EXP];
            copy(arr, mat);
            calc(arr, n - 3, ans);
            ll res = 0;
            rep(i, expo) {
                rep(j, expo) {
                    res = (res + ans[i][j])%mod;
                }
            }
            pl(res);
            pn;
        }
    }
    return 0;
}