5176 - 数论:卡特兰数:直线走法【模板】

通过次数

19

提交次数

22

时间限制 : 1 秒
内存限制 : 128 MB

在直角坐标系中,从(0,0)出发,每次只能向上走或向右走,且不能越过y=x这条直线(可以在线上),求走到(n,n)的不同路径的数量

输入

输入1个整数n n<=25

输出

输出一个数字

样例

输入

5

输出

42

提示

20%测试点 n<=5
80%测试点 n<=25