U215548 卡特兰数

这里有一个经典的组合计数问题（这是2009年全国高中数学联赛河北省预赛试题）： >$10$个人去买票，其中$5$个人每人只有五元纸币一张，另外$5$个人每人只有十元纸币一张。 > >售票处初始的时候没有任何零钱。 > >如果只关心每个人的持有的纸币面值（例如，持有五元纸币的人视作相同的），那么这些人有几种来买票的先后顺序，使售票处总能顺利找零。 这个问题与“从正方网格中，从左下角走最短路到右上角，但不穿越图中对角线”的走法数完全等价。 因为可以认为一次向右对应一个五元的人买票，一次向上对应一个十元的人买票，则“不超过对角线”等价于“任何时刻向右次数不少于向上次数”等价于“任何时刻五元人数不少于十元人数”等价于“总能顺利找零”。  买票问题的答案为“卡特兰数”$C_5=42$。上图走格子方法数则为“卡特兰数”$C_4=14$。实际上，若持有五元、十元纸币的各有$n$人，或正方形边长为$n$，则方法数为“卡特兰数”$C_n$。 “卡特兰数”是组合计数问题中较为高级，但十分常用的一个数列，一般用$C_0,C_1,\cdots,C_n,\cdots$表示，其中 $C_n=1\quad (n=0)$ $C_{n}=C_0\times C_{n-1}+C_1\times C_{n-2}+\cdots +C_{n-1}\times C_0 \quad (n>0)$ 本题中，通过$n$，请计算得到$C_n$并输出。

一个整数$n$。

一行，一个数，即卡特兰数$C_n$。 保证这个数可以用`long long`类型存储。

$0\le n \le 25$。