#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

template <int N, int P>
struct Vector
{
    int Item[N];
    Vector()
    {
        for (int i = 0; i < N; ++i)
            Item[i] = 0;
    }
    Vector(initializer_list<int> l)
    {
        int i = 0;
        for (auto x = l.begin(); x != l.end() && i < N; ++x)
            Item[i++] = *x;
        while (i < N)
            Item[i++] = 0;
    }
    int &operator[](int _i) { return Item[_i]; }
    friend int operator*(const Vector a, const Vector b)
    {
        int result = 0;
        for (int i = 0; i < N; ++i)
            result = (result + a.Item[i] * (i64)b.Item[i]) % P;
        return result;
    }
    friend ostream &operator<<(ostream &os, const Vector v)
    {
        os << '[';
        for (int i = 0; i < N; ++i)
        {
            if (i != 0)
                os << ',';
            os << v.Item[i];
        }
        os << ']';
        return os;
    }
};

template <int N, int P>
struct Matrix
{
    typedef Vector<N, P> Vec;
    Vec Item[N];
    Matrix() {}
    Matrix(initializer_list<initializer_list<int>> l)
    {
        int i = 0;
        for (auto x = l.begin(); x != l.end() && i < N; ++x)
            Item[i++] = Vec(*x);
        while (i < N)
            Item[i++] = Vec({0});
    }
    static Matrix Identity()
    {
        Matrix result;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                result[i][j] = i == j ? 1 : 0;
        return result;
    }
    Vec &operator[](int _i) { return Item[_i]; }
    Matrix Transpose()
    {
        Matrix result;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                result[i][j] = Item[j][i];
        return result;
    }
    friend Vec operator*(const Matrix a, const Vec b)
    {
        Vec result;
        for (int i = 0; i < N; ++i)
            result[i] = a.Item[i] * b;
        return result;
    }
    friend Matrix operator*(const Matrix a, const Matrix b)
    {
        Matrix result;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
            {
                int tmp = 0;
                for (int k = 0; k < N; ++k)
                    tmp = (tmp + a.Item[i].Item[k] * (i64)b.Item[k].Item[j]) % P;
                result[i][j] = tmp;
            }
        return result;
    }
    friend ostream &operator<<(ostream &os, const Matrix m)
    {
        os << '[';
        for (int i = 0; i < N; ++i)
        {
            if (i != 0)
                os << ',';
            os << m.Item[i];
        }
        os << ']';
        return os;
    }
};

/*
f[p,n] 
    = f[p-1,n-u]*(u/2+1)*(u-u/2)        for u in 1..n
    = f[p-1,n-1] + 2*() + 4*() + 6*() + 9*() + 12*() + ...
    = f[p,n-2] + i*f[p-1,n-i]           for i in 1..n
    = f[p,n-2] + g[p,n]
g[p,n] 
    = i*f[p-1,n-i]                      for i in 1..n
    = g[p,n-1] + f[p-1,n-i]             for i in 1..n
    = g[p,n-1] + h[p,n]
h[p,n] 
    = f[p-1,n-i]                        for i in 1..n
    = h[p,n-1] + f[p-1,n-1]
f[0,0] = 0
f[0,_] = 1
f[1,1] = 1

v = {
    f[0,_] ( === 1 ),
    f[1,n], f[1,n-1],   f[1,n-2],   g[1,n], g[1,n-1],   h[1,n],
    f[2,n], f[2,n-1],   f[2,n-2],   g[2,n], g[2,n-1],   h[2,n],
    f[3,n], f[3,n-1],   f[3,n-2],   g[3,n], g[3,n-1],   h[3,n],
    f[4,n], f[4,n-1],   f[4,n-2],   g[4,n], g[4,n-1],   h[4,n],
    f[5,n], f[5,n-1],   f[5,n-2],   g[5,n], g[5,n-1],   h[5,n],
}
*/

constexpr int f(int i, int j = 0) { return i == 0 ? 0 : (i - 1) * 6 - j + 1; }
constexpr int g(int i, int j) { return (i - 1) * 6 - j + 4; }
constexpr int h(int i, int j = 0) { return i * 6; }
constexpr int sf(int i, int j = 0) { return i == 0 ? 0 : f(i, j) - 1; }
constexpr int sg(int i, int j) { return g(i, j) - 1; }
constexpr int sh(int i, int j = -1) { return h(i); }

template <int N, int P>
#define Mat Matrix<N, P>
Mat Exp(const Mat e, int p)
{
    Mat result = Mat::Identity(), tmp = e;
    for (; p > 0; p >>= 1)
    {
        if (p & 1)
            result = tmp * result;
        tmp = tmp * tmp;
    }
    return result;
}

int main()
{
    Matrix<31, 1000000007> m;
    auto dep = [&m](int x, initializer_list<int> y) {
        for (auto _y = y.begin(); _y != y.end(); ++_y)
            m[x][*_y] = 1;
    };
    dep(0, {0});
    for (int i = 1; i <= 5; ++i)
    {
        dep(h(i), {sh(i), sf(i - 1, -1)});
        dep(g(i, 0), {sg(i, -1), sh(i), sf(i - 1, -1)});
        dep(g(i, -1), {sg(i, -1)});
        dep(f(i, 0), {sf(i, -2), sg(i, -1), sh(i), sf(i - 1, -1)});
        dep(f(i, -1), {sf(i, -1)});
        dep(f(i, -2), {sf(i, -2)});
    }
    Vector<31, 1000000007> v{
        1,
        3, 1, 0, 3, 1, 2,
        1, 0, 0, 1, 0, 1,
        0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0};
    int T, n;
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--)
    {
        cin >> n;
        cout << (n < 5 ? 0 : ((Exp(m, n - 2) * v)[25])) << '\n';
    }
}

Measured memory_bytes: 3636