#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int g_bm = 1000000007;

#define _LL long long

int modl(_LL a)
{
    a %= g_bm;
    if( a < 0 ) a += g_bm * ( 1 - (a + 1) / g_bm );
    return a;
}

int modadd(_LL a, _LL b)
{
    return modl(a + b);
}

int modminus(_LL a, _LL b)
{
    return modl(a - b);
}

int modmul(_LL a, _LL b)
{
    return modl(a * b);    
}

int modpow(_LL a, _LL b)
{
    int prebit = modl(a);
    int ans = 1;
    for( int bit = 0; (long unsigned int) b >= (1UL << bit); bit++ )
    {
        if( bit > 0 ) prebit = modmul(prebit, prebit);
        if( b & (1UL << bit) ) ans = modmul(ans, prebit);
    }
    return ans;
}

int modcalcsub(_LL a, _LL b, char c)
{
    switch(c)
    {
        case '+':
            return modadd(a, b);
        case '-':
            return modminus(a, b);
        case '*':
            return modmul(a, b);
    }
    return 0;
}

int modsublevel(char c)
{
    switch(c)
    {
        case '+':
        case '-':
            return 0;
        case '*':
            return 1;
    }
    return 0;
}

int modinv(_LL a) 
{
    _LL b = g_bm, u = 1, v = 0;
    while (b) 
    {
        _LL t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    return modl(u);
}

int modcalc(_LL a1, char c1, _LL a2, char c2 = 0, _LL a3 = 0, char c3 = 0, _LL a4 = 0, char c4 = 0, _LL a5 = 0, char c5 = 0)
{
    char c[6] = {c1, c2, c3, c4, c5, '0'};
    _LL a[6] = {a1, a2, a3, a4, a5, 0};
    int ans[4];
    char prec[4];
    int level = 0;
    int index = 0;
    ans[0] = 0;
    prec[0] = '+';
    // 3 + 4 * 8 + 3
    while( prec[level] != '\0' )
    {
        int nlevel = modsublevel(c[index]);
        while( level < nlevel )
        {
            ans[level + 1] = 0;
            prec[level + 1] = '+';
            level++;
        }        
        ans[level] = modcalcsub( ans[level], a[index], prec[level]);
        while( nlevel < level )
        {
            ans[level - 1] = modcalcsub( ans[level - 1], ans[level], prec[level - 1]);
            level--;
        }
        prec[level] = c[index++];
    }
    return ans[0];
}

class ModFactorial
{
public:
    int m_max;
    int *m_factorial;
    int *m_factorialinv;

    ModFactorial(int max)
    {
        m_max = max + 1;
        m_factorial = (int*) malloc(sizeof(int) * m_max );
        m_factorialinv = (int*) malloc(sizeof(int) * m_max );
 
        m_factorial[0] = 1;
        for( int k = 1; k < m_max; k++) m_factorial[k] = modmul(k, m_factorial[k - 1]);
        m_factorialinv[m_max - 1] = modinv( m_factorial[m_max - 1] );
        for( int k = m_max - 1 ; k > 0; k--) m_factorialinv[k - 1] = modmul(k, m_factorialinv[k]);
    }

    ~ModFactorial()
    {
        free(m_factorial);
        free(m_factorialinv);
    }

    int getFactorial(int n)
    {
        return m_factorial[n];
    }

    int getFactorialInv(int n)
    {
        return m_factorialinv[n];
    }

    int getCombination(int n, int r)
    {
        return modcalc(m_factorial[n], '*', m_factorialinv[r], '*', m_factorialinv[n - r]);
    }
};

inline static int _getindexmodarray(int c, int r, int w, int h)
{
    return r * w + c;
}

class modArray
{
    public:
        int* _a;
        int w;
        int h;

        modArray()
        {
            w = 0; h = 0; _a = NULL;
        }
        modArray(const modArray &src)
        {
            w = src.w;
            h = src.h;
            _a = new int[w * h];
            memcpy(_a, src._a, w * h * sizeof(int));
        }

        modArray(int tw, int th)
        {
            w = tw;
            h = th;
            _a = new int[w * h];
            for( int r = 0; r < h; r++)
                for( int c = 0; c < w; c++ )
                    _a[_getindexmodarray(c, r, w, h)] = ( r == c ? 1 : 0);
        }

        modArray(int *a, int tw, int th)
        {
            w = tw; h = th;
            _a = new int[w * h];
            memcpy(_a, a, w * h * sizeof(int));
        }

        modArray(const vector<int> &v, int tw, int th)
        {
            w = tw; h = th;
            _a = new int[w * h];
            for( int r = 0; r < h; r++)
                for( int c = 0; c < w; c++ )
                    _a[_getindexmodarray(c, r, w, h)] = v[c + r * w];
        }

        ~modArray()
        {
            if( _a != NULL ) delete _a;
        }

        modArray& operator = ( const modArray& b )
        {
            if( w != b.w && h != b.h )
            {
                if( _a != NULL ) delete _a;
                w = b.w;
                h = b.w;
                 _a = new int[w * h];
            }
            memcpy(_a, b._a, w * h * sizeof(int));
            return *this;
        }

        int *operator[](int r)
        {
            return _a + (r * w);
        }

        void set(int r, int c, int n)
        {
            _a[_getindexmodarray(c, r, w, h)] = n;
        }

        int at(int r, int c) const
        {
            return  _a[_getindexmodarray(c, r, w, h)];
        }

        const modArray operator * (const modArray &b) const
        {
            // w == b.h, h == b.w
            modArray ans(w, h);
            for( int r = 0; r < h; r++)
                for( int c = 0; c < w; c++ )
                {
                    int t = 0;
                    for( int i = 0; i < w; i++ )
                    {
                        t = modadd(t, modmul(at(r, i), b.at(i, c)));                        
                    }
                    ans.set(r, c, t);
                }
            return ans;
        }

        modArray& operator *= ( const modArray& b )
        {
            *this = *this * b; 
            return (*this);
        }

        modArray* getPow(int n) const
        {
            // w == h
            modArray *ans = new modArray(w, h);   
            modArray bitpow(*this);
            for( int bit = 0; (long unsigned int) n >= (1UL << bit); bit++ )
            {
                if( bit > 0 ) bitpow *= bitpow;
                if( n & (1UL << bit) ) *ans *= bitpow;
            }
            return ans;            
        }

        void print() const
        {
            for(int r = 0; r < h; r++)
            {                
                for( int c = 0; c < w; c++)
                {
                    cout << at(r, c) << " ";
                }
                cout << endl;
            }
            cout << endl;
        }
};

class modVector
{
    public:
        int* _a;
        int _l;

        modVector()
        {
            _a = NULL; _l = 0;
        }

        modVector(int n)
        {
            _l = n;
            _a = new int[_l];
            memset(_a, 0, _l * sizeof(int));
        }

        modVector(const modVector& src)
        {
            _l = src._l;
            _a = new int[_l];   
            memcpy(_a, src._a, _l * sizeof(int));         
        }

        modVector(int *a, int n)
        {
            _l = n;
            _a = new int[_l];   
            memcpy(_a, a, _l * sizeof(int));         
        } 

        modVector(const vector<int> &v)
        {
            _l = (int) v.size();
            _a = new int[_l];   
            for( int i = 0; i < _l; i++ ) _a[i] = v[i];
        }
        modVector& operator = ( const modVector& b )
        {
            if( _l != b._l )
            {
                if( _a != NULL ) delete _a;
                _l = b._l;
                _a = new int[_l];
            }
            memcpy(_a, b._a, _l * sizeof(int));
            return *this;
        }

        ~modVector()
        {
            if(_a != NULL) delete _a;
        }

        int& operator[](int k)
        {
            return _a[k];
        }

        int get(int k) const
        {
            return _a[k];
        }

        const modVector operator + (const modVector &b) const
        {
            // w == b.h, h == b.w
            modVector ans(*this);
            ans += b;
            return ans;
        }

        modVector& operator += ( const modVector& b )
        {
            for( int i = 0; i < _l; i++ ) _a[i] += b.get(i); 
            return (*this);
        }

        const modVector operator * (const modArray &b) const
        {
            // _l == b.w
            modVector ans(_l);
            for( int r = 0; r < _l; r++)
            {
                int t = 0;
                for( int i = 0; i < _l; i++ )
                {
                    t = modadd(t, modmul(get(i), b.at(r, i)));                        
                }
                ans[r] = t;
            }
            return ans;
        }

        modVector& operator *= ( const modArray& b )
        {
            *this = *this * b; 
            return (*this);
        }        

        void print() const
        {
            for( int i = 0; i < _l; i++ ) cout << _a[i] << " ";
            cout << endl;
        }        
};

int main()
{
    int t;
    cin >> t;

    modArray a(21, 21);
    for( int i = 0; i < 5; i++)
    {
        for( int j = 0; j < 21; j++)
        {
            a[i * 2][j] = 0;
            a[i * 2 + 1][j] = 0;
        }
        if( i > 0 ) a[i * 2][(i - 1) * 2] = 1;
        a[i * 2][i * 2 + 1] = 1;
        a[i * 2 + 1][i * 2] = 1;
    }
    for( int i = 5; i <= 15; i++)
    {
        for( int j = 0; j < 21; j++) a[i + 5][j] = (( i + 5 == j) ? 1 : 0);
        if( i == 5)
        {
            a[i + 5][4 * 2] = 1;
        } 
        else 
        {
            a[i + 5][i + 4] = 1;
        }
    }

    
        
    for( int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        modArray *p = a.getPow(n + 10);
        modVector v(21);
        v[0] = 1;
        v *= *p;
        cout << v[20] << endl;
        delete p;
    }
}

Measured memory_bytes: 3640