#include <bits/stdc++.h>
#define INT long long int
#define MOD 1000000007
INT n, dp[10010][10010];

using namespace std;
INT f(int x, int y)
{
 if( x > n or y > n ) return 0;
 if( x == n and y == n ) return 1;
 if( x == y and x ) return 0;
 if( ~dp[x][y] ) return dp[x][y];
 INT &ret = dp[x][y] = 0;
 if( x > y ) ret += f(x, y+1)+f(x,y+2)+f(x,y+3)+f(x,y+4);
 if( x <= y ) ret += f(x+1,y)+f(x+2,y)+f(x+3,y);
 ret %= MOD;
 return ret;
}

int main()
{
    srand(time(NULL));
    char S[110];
    int T;
    cin>>T;
    for(int t = 1 ; t <= T ; t++)
    {
        int l;
        char s[10010] = {0};
        scanf("%d", &l);

        sprintf(S, ".%d.in", t);
        FILE *in = fopen(S, "w");
        fprintf(in, "%d\n", l);
        fclose(in);

        memset(dp, -1, sizeof(dp));
        n = l;

        sprintf(S, ".%d.out", t);
        FILE *out = fopen(S, "w");
        fprintf(out, "%lld\n", f(0,0));
        fclose(out);
    }
}