You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。比如当n=6时，f（6）=14。

有趣的是 合法括号表达式的个数和这个是一样的。 括号表达式指只由(和)组成的表达式，合法指的是括号能合理配对。

如 $n=1$ 时，1对括号中，合法的括号表达式有1个：() ；不合法的括号表达式也有一个：)(。

如 $n=2$ 时，2对括号中，合法的括号表达式有2个： ()() 和 (()).

n个 合法括号序列 的答案为g(n)，那么 g(n) = f(n+2)

求g(n)。

输入格式

一行一个正整数 $n$

输出格式

方案数g(n)

4

14

6

132

数据范围

$n \le 20$