#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <iomanip>

using namespace std;

#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (b) - 1; i >= (a); i--)

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())

typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;

const ll mod = 1000000007;
ll powmod(ll a, ll b) { ll res = 1; a %= mod; for (; b; b >>= 1) { if (b & 1) res = res*a%mod; a = a*a%mod; } return res; }

ll dp[2005][26][4];

int main() {
    rep(i, 0, 26) {
        dp[1][i][1] = 1;
    }
    rep(i, 2, 2002) {
        rep(j, 0, 26) {
            rep(k, 1, min(4, i + 1)) {
                ////
                if (k == 1) {
                    rep(a1, 0, 26) {
                        rep(a2, 1, 4) {
                            if (a1 == j) break;
                            dp[i][j][k] += dp[i - 1][a1][a2];
                            if (dp[i][j][k] >= mod) dp[i][j][k] -= mod;
                        }
                    }
                }
                else {
                    dp[i][j][k] += dp[i - 1][j][k - 1];
                    if (dp[i][j][k] >= mod) dp[i][j][k] -= mod;
                }
                ////
            }
        }
    }

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        ll ans = 0;
        rep(i, 0, 26) {
            rep(j, 1, min(4, n + 1)) {
                ans += dp[n][i][j];
                if (ans >= mod) ans -= mod;
            }
        }
        cout << ans << endl;
    }
    return 0;
}