题目描述

xz上课给同学们讲了二叉树问题，求n个节点能构成多少个形状不同的二叉树，并于上课推到出来，先取一个点作为顶点,然后左边依次可以取0至N-1个相对应的,右边是N-1到0个,两两配对相乘,就是h(n)=h(i)= h(0)*h(i-1)+h(1)*h(i-2) + ... + h(i-1)h(0)，(n>=2时成立，h(n)为n个节点能构成多少个形状不同的二叉树数量，特别的n xz相信你们都回家做了这个作业，所以出了一道题来考考你，求有n+1个叶子的二叉树的个数。 例如当n=3时，那么有( n+1 ) = 4个叶子。

输入格式

输入包含多组测试数据。  每组测试数据共一行，给出一个整数n.(0<n<=30)

输出格式

每行输出一个整数ans表示答案。

3

5