题目描述

二叉树是每个节点最多有两个子节点的树。给定一个整数n，求以n为节点数组成的二叉树有多少种？

例如当n=3时，有5种二叉树（如图）。

输入格式

一个正整数n(1≤n≤10)。

输出格式

一个整数，为二叉树的种类数。

输入/输出样例

3

5

说明/提示

时间1000ms，内存256MiB