# Appreciation

/*
 * Problem :: 4811 / 알약
 *
 * Kind :: Dynamic Programming + Math
 *
 * Insight
 * - 일단은 알약 반개를 꺼내려면 그전에 알약 한개를 꺼내야 한다
 *   + W W W H H H 는 알약 한개를 연달아 세번 꺼냈으니
 *     알약 반개를 연달아 세번 꺼낼 수 있지만
 *     W H H W W H 는 알약 한개를 꺼냈는데 그 다음에 알약 반개를 연달아 두번 꺼내니
 *     불가능한 문자열이다
 *     # 즉 문자열에서 H 가 있을 때, 그 때까지 나온 H 의 개수는 W 의 개수보다 많을 수 없다
 *
 * - N=1 / W H / 1가지
 *   + (W,H) 1쌍
 *   N=2 / W W H H, W H W H / 2가지
 *   + (W,H) 2쌍
 *   N=3 / W W W H H H, W W H H W H, W H W H W H, W H W W H H, W W H W H H / 5가지
 *   + (W,H) 3쌍
 *   ...
 *   + N=k 일 때, 문자열을
 *     W (A) H (B) 로 나타낼 수 있다.
 *     A 문자열에 (W,H) i 쌍이 들어간다면
 *     B 문자열에 (W,H) k-1-i 쌍이 들어가야 한다
 *     # 중요한 것은 A 문자열, B 문자열 모두 W 로 시작하고 H 로 끝나기 때문에
 *       위의 정의에서 겹치는 경우는 발생하지 않는다!
 *       -> N=2 일 때,
 *          W () H (W H) => W H W H
 *          W (W H) H () => W W H H
 *
 * - 따라서 점화식은 다음과 같다
 *   dp[i] = dp[0] * dp[i-1]
 *           + dp[1] * dp[i-2]
 *           + ...
 *           + dp[i-2] * dp[1]
 *           + dp[i-1] * dp[0]
 *
 * Point
 * - 예제가 꽤 친절하다
 *   + dp[1], dp[2], dp[3], dp[4] 값도 알려주고
 *     dp[30] 의 값도 알려줘서 Overflow 주의를 준다
 *
 * - 사실 이 문제는 '카탈란 수'를 다루는 문제이다
 *   + W 를 '(' 로 H 를 ')' 로 본다면
 *     이는 N 쌍의 괄호가 주어졌을 때 올바른 괄호열이 모두 몇개인지를 구하는 문제와 같다
 *     # 신기신기 ~ (카탈란 수를 검색해보자)
 *
 * - 솔직히 고백하건대 처음 풀때는 그냥 감으로 풀었다
 *   알약 3개는 알약 1개와 알약 2개의 경우로 나눌 수 있지 않을까? 하다가
 *   우연히 알약 3개의 경우의 수가
 *   (알약 0개 * 알약 2개 + 알약 1개 * 알약 1개 + 알약 2개 * 알약 0개) 와 같아서
 *   이렇게 풀면 되지 않을까 하고 찍었는데 맞았다
 *   # 다른 사람들의 풀이를 봤는데
 *     dp[i][j] = dp[i-1][j] + dp[i][j-1] 로 많이 풀었다
 *     -> 사실 바로 위의 풀이가 좀더 직관적이고 생각하기 쉬운 것 같다
 *        내심 나는 쉽게 생각할 수 있는 것을 어렵게 생각하는 습관이 있는 것 같아 좀 걱정된다...
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Process
    long dp[30+1]; /* 카탈란 수 */
    memset(dp, 0, sizeof(dp));
    dp[0] = 1; /* (W,H) 가 0 쌍일 때 가능한 문자열의 개수는 빈 문자열 1가지 */
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 5;
    dp[4] = 14;
    for (int i=5; i<=30; i++) {
        for (int j=0; j<i; j++) {
            dp[i] += dp[j] * dp[i-1-j];
        }
    }

    // Set up : Input
    while (true) {
        int N; cin >> N;
        if (N == 0) break;

        // Control : Output
        cout << dp[N] << endl;
    }
}

// Helper Functions
/* None */