### 问题描述 卡特兰遇到了一个非常棘手的问题，他现在有许多对括号，他想知道这些括号有多少种有效的组合方式。 一个有效的括号配对定义为： 1. 每个开括号 `(` 后面都必须在某个位置有一个对应的闭括号 `)`。 2. 对于任意位置，从字符串的开始到这个位置，开括号的数量都不少于闭括号的数量。换句话说，在任何时刻，不能出现已经关闭的括号数量超过已经打开的括号数量的情况。 利用这些定义，我们可以确保： 1. 所有开括号都有闭括号与之配对。 2. 不会出现像 `)(` 这样的无效组合。 3. 字符串中的每一个括号都有其有效的作用，没有多余的开或闭括号。 给定一个整数 $n$，代表 $n$ 对括号。你的任务是确定这 $n$ 对括号能够生成多少种有效的配对方法。一个有效的括号配对是指每一个开括号都与一个闭括号正确配对，并且没有多余的开或闭括号。 例如，对于 $n = 3$，存在的有效配对有 `((()))`，`(()())`，`(())()`，`()(())` 与 `()()()`。 ### 输入格式 一个整数 $n$，$(1 \le n \le 30)$，代表括号的对数。 ### 输出格式 一个整数，表示 $n$ 对括号能形成的有效配对方法数。 ### 样例输入 ``` 3 ``` ### 样例输出 ``` 5 ``` ### 样例说明 如上述问题描述中提到的，对于 $n = 3$，存在的有效配对有 $5$ 种：`((()))`，`(()())`，`(())()`，`()(())` 与 `()()()`。 ### 测评数据规模 输入中的整数 $n$ 满足 $1 \le n \le 30$。