括号化问题（卡特兰数应用）

题目描述

P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？

输入格式

输入一个数字n，代表有n个数相乘。(n<30)

输出格式

输出其括号化的方案数。

样例 #1

样例输入 #1

4

样例输出 #1

5

提示

【样例解释】

n=4,表示有四个数相乘，假设为1x2x3x4,则其括号化可以是：

1x(2x(3x4))

1x((2x3)x4)

(1x2)x(3x4)

((1x2)x3)x4

(1x(2x3))x4