• 폴������������
  
• 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;
}