描述

求由n个结点构成的不同的二叉树数.

格式

输入格式

一行，包含一个整数n(1<=n<=5000)。

输出格式

输出一个整数，表示由n个结点构成的不同的二叉树数.

样例1

样例输入1

3

样例输出1

5

限制

时限1s