/**
* POLY
*/
#include <stdio.h>
#define N 92
#define MAX_N 100
//인덱스 처리가 1~100 까지 되므로 101 로 해줌
int cache[MAX_N+1][MAX_N+1];
const int mod = 10*1000*1000;
//n개의 정사각형이 있고 첫 줄을 first 로
//고정하면 몇개의 polynomio 가 만들어 지는가?
//값이 커서 나머지를 구하는 경우 부분 나머지를 먼저 구해도 상관없음
//굳이 크기를 비교하지 않아도 지장 없음.
//단, 특정 수 초과시 나머지를 구한다면 크기비교 필요.
int poly(int n, int first){
//기저사례
if(n==first){
return 1;
}
//메모이제이션
int &ret = cache[n][first];
if(ret!=-1) {
return ret;
}
//hypothesis = poly(n-i,i)
//다음번 n은 반드시 n-first 이다.
//poly(n-first, 1) ~ poly(n-first, n-first);
ret =0;
for(int second=1;second<=n-first;second++){
int add = first+second -1;
add *= poly(n-first,second);
add %= mod;
ret += add;
ret %= mod;
}
return ret;
}
int main(){
//cache initialization
int i=0,j=0,n=0;
for(i=0;i<=MAX_N;i++){
for(j=0;j<=MAX_N;j++){
cache[i][j]=-1;
}
}
for(i=1;i<=N;i++){
n+=poly(N,i);
n%=mod;
}
printf("%d
",n);
}