264p 폴리노미오

#include<iostream>

using namespace std;

long long d[101][101];

int dp(int n, int first)

{

if(n==first)return 1;

if(n<first)return 0;

long long  &ret = d[n][first];

if(ret != -1 ) return ret;

long long  ans = 0;

for(int second = 1; second<=n-first; second++)

{

ans += dp(n-first, second)*(first+second-1);

ans%=10000000;

}

return ret = ans;

}

int main()

{

int C,n;

cin>>C;

memset(d,-1,sizeof(d));

while(C--)

{

cin>>n;

long long  ans = 0;

for(int first = 1; first<=n; first++)

{

ans += dp(n, first);

ans%=10000000;

}

cout<<ans<<endl;

}

}