背景

卡特兰数，又称卡塔兰数、明安图数，是组合数学中一种常出现于各种计数问题中的数列。以比利时数学家欧仁·查理·卡特兰的名字命名。

描述

已知卡特兰数的前四项为1, 1, 2, 5 且满足以下递推关系：

求第N项卡特兰数

格式

输入

一个正整数 N（不为0）

输出

卡特兰数的第N项

示例

输入

5

输出

14

限制

限时1000ms 空间限制20MB