算法题：UVA 991 - Safe Salutations （卡特兰数）

算法题：UVA 991 - Safe Salutations （卡特兰数）2014-04-20 csdn accelerator_Safe Salutations

Problem

As any minimally superstitious person knows all too well, terriblethings will happen when four persons do a crossed handshake.

You, an intrepid computer scientist, are given the task of easing theburden of these people by providing them with the feasible set ofhandshakes that include everyone in the group while avoiding any suchcrossings. The following figure illustrates the case for 3 pairs ofpersons:

Input

The input to this problem contains several datasets separated by a blank line. Each dataset is simply an integern, the number ofpairs of people in the group, with 1 ≤ n ≤ 10.

Output

The output is equally simple. For each dataset, print a single integer indicating the numberof possible crossless handshakes that involve everyone in a groupwithn pairs of people. Print a blank line between datasets.

Sample Input

Sample Output