#include <cstdio>
#include <algorithm>
#include <cstring>
#define REP(i,a,b) for (int i=a;i<=b;++i)
using namespace std;

const int mo=1000000007;
int f[2001][4][26];
int main(){
    int T,n; scanf("%d",&T);
    while (T--){
       scanf("%d",&n);
       memset(f,0,sizeof(f));
       REP(i,0,25) f[1][1][i]=1;
       REP(i,2,n){
          REP(j,0,25)
             REP(k,2,3)
               f[i][k][j]=f[i-1][k-1][j];
          REP(j,0,25)
             REP(k,0,25) if (j!=k)
                REP(l,1,3) (f[i][1][j]+=f[i-1][l][k])%=mo;
       }
       int ans=0;
       REP(j,1,3) REP(k,0,25) (ans+=f[n][j][k])%=mo;
       printf("%d\n",ans);
             
    }
    return 0;
}