#include<bits/stdc++.h>
#define mems(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
const int MS=30,mod=1e9+7;
struct Mat//矩阵
{
    ll a[MS][MS];
    int n,m;
    Mat(int n=0,int m=0):n(n),m(m) { mems(a,0);}
    Mat operator*(const Mat&B)const
    {
        Mat C(n,B.m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=B.m;j++)
                for(int k=1;k<=m;k++)
                C.a[i][j]=(C.a[i][j]+a[i][k]*B.a[k][j])%mod;
        return C;
    }
};
Mat qpow(Mat a,int n)
{
    Mat ans(a.n,a.n);
    for(int i=1;i<=a.n;i++) ans.a[i][i]=1;
    while(n)
    {
        if(n&1) ans=ans*a;
        a=a*a;
        n>>=1;
    }
    return ans;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        int n;scanf("%d",&n);
        n+=10;
        Mat A(21,21);
        for(int i=1;i<=5;i++) A.a[16+i][i]=1;
        for(int i=2;i<=5;i++) A.a[i-1][i]=1;
        for(int i=6;i<=16;i++) A.a[i-1][i]=A.a[i][i]=1;
        for(int i=17;i<=21;i++) A.a[i-16][i]=1;
        A=qpow(A,n);
        printf("%lld\n",A.a[1][16]);
    }
}

