AC

#include <iostream>
#include <vector>

using namespace std;

int main() {

int n;
cin >> n;

vector<long long> dp(n + 1, 0);
dp[0] = 1;

for (int i = 1; i <= n; ++i) {
    for (int k = 1; k <= i; ++k) {
        dp[i] += dp[k - 1] * dp[i - k];
    }
}

cout << dp[n] << endl;

return 0;

}