#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#include<string>

#include<vector>

#include<iostream>

#include<set>

#include<cstring>

#include<queue>

#include<map>

#define inf 0x3f3f3f3f

#define ll long long

using namespace std;

const int p=1e9+;

int a[]={,,,,,,,,,,,,};

int dp[];

int main()

{

    memset(dp,,sizeof(dp));

    dp[]=;

    for(int i=;i<;i++)

    {

        for(int j=a[i];j<=;j++)

            dp[j]=( dp[j] + dp[ j-a[i] ] )%p;

    }

    int n,t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        printf("%d\n",dp[n]);

    }

    return ;

}