买票（卡特兰数应用）

题目描述

有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中排队方法使得只要有10元的人买票，售票处就有5元的钞票找零？

输入格式

输入一个正整数n,(n<=10)

输出格式

输出方案数。

样例 #1

样例输入 #1

2

样例输出 #1

8

样例 #2

样例输入 #2

3

样例输出 #2

180

题解