C++ :

#include<iostream>
#include<algorithm>

using namespace std;

long long f[1001] = {0, 1, 1, 2};

inline long long search(int T)
{
	if(f[T])return f[T];
	for(int i = 1; i < T; i++)
	{
		f[T] += search(T - i) * search(i);
	}
	return f[T];
}

int main()
{
	int n;
	while(cin >> n)cout << search(n) << endl;
	return 0;
}