• ���리���미노
  
• 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;
}