Alien language

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define N 200000
#pragma comment(linker, "/stack:200000000")

ll n;

ll dp[N+10][6];

ll rec(ll level, ll last){
    if(level==N-1) return 1;
    if(dp[level][last]!=-1){
        return dp[level][last];
    }
    ll ans;
    if(last==1){
        ans= rec(level+1,2);
    }
    else if(last==2){
        ans = rec(level+1,3)+rec(level+1,4);
    }
    else if(last==3){
        ans = rec(level+1,5)+rec(level+1,1) +rec(level+1,2);
    }
    else if(last==4){
        ans = rec(level+1,5)+rec(level+1,1) +rec(level+1,2) + rec(level+1,3)+rec(level+1,4);
    }
    else {
        ans = rec(level+1,1);
    }
    ans %=mod;
    return dp[level][last]=ans;
}

void solve(){
    cin>>n;
    ll temp = rec(N-n,5)+rec(N-n,1) +rec(N-n,2) + rec(N-n,3)+rec(N-n,4);
    cout<<temp%mod<<endl;
}	

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    memset(dp,-1,sizeof(dp));
    ll _t;cin>>_t;
    ll _waste = rec(0,1) +rec(0,2) + rec(0,3)+rec(0,4)+rec(0,5);
    while(_t--)
	    solve();
}