• ���리���미노
  
• DP를 ��������� 문���.
  
  • 가로������ ������라 ���고, X개로 만드는 것��� 경���는
    
    • X-1개(������ ��������� ���������고) + ������ ������ 1개 , X-2개 + ��������� 2개, ... , 1개 + ��������� X-1개, ��������� X개 로 ���갤 ��� ���다.
      
    • ���때, ������ ��������� ��������� 것��� ������ ��������� 개���가 몇개������ ���������데, ��������� 개������ 두����������� 개������ ������ ���리���미노를 만������는 경������ ���가 ��������되기 때문���다.
      
    • (���를들��� ��������� 3개, 두�������� 2개(그 ���래������ ���관������)��� 경���는 " ��������� + 두�������� - 1 ", ��� 4개��� 경���가 ���기고, ���를 �����������다.
      
      • ���기까��� ������를 ���다면 ������ DP ������������ 만들���보고, 그렇��� ���다면 ���드를 보고 ���������보려고 노력���보���. ������로 ������미��� ���드는 3����� for문과 ��������� ������, ��� 두��� 뿐���라는 것��� ���게 될 것���다.
        

//
//  main.cpp
//  Algospot_normal
//
//  Created by Jereneal Kim on 13. 8. 15..
//  Copyright (c) 2013�� Jereneal Kim. All rights reserved.
//

#include <iostream>
using namespace std;
int dp[101][101] = {0};
int main(int argc, const char * argv[])
{
	int i,j,level,n,T;
	dp[1][1]=1;
	for(level=2;level<=100;level++){
		for(i=1;i<level;i++){
			for(j=1;j+i<=level;j++){
				dp[level][i] %= 10000000;
				dp[level][i] += (i+j-1)*dp[level-i][j];
			}
		}
		dp[level][i]=1;
	}
	scanf("%d",&T);
	for(int iter=0;iter<T;iter++){
		scanf("%d",&n);
		int sum=0;
		for(i=1;i<=n;i++){
			sum=(sum+dp[n][i])%10000000;
		}
		printf("%d\n",sum);
	}
	return 0;
}