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