时间限制： 1.0 秒

空间限制： 256 MB

题目描述

AZY 童鞋很喜欢有美感的艺术设计，有一天他看到了这样一种由圆形和线段构成的图案。

显然，上图中有 $15$ 个节点（圆形）。除了最底下的绿色节点，每个节点都有两个“下属节点”。

AZY 发现，这种图案有几个特点：

• 每个节点至多只有二个“下属节点”。
• 如果颠倒过来看，很像是一颗不断分叉的小树。（废话）

现在，AZY 知道了图案中一共有 $n$ 个节点，那么不重样的图案总数会是多少呢？AZY 已经帮你画出了 $n = 3$ 时的所有图案：

现在请你回答 AZY，当 $n$ 为其他数值时，不同结构的图案数一共多少？

输入格式

从标准输入读入数据。

仅一个正整数 $n$，表示节点个数。

输出格式

输出到标准输出。

输出一个非负整数，为不同结构的图案数。

3

5

子任务

对于所有数据，保证 $n\le 20$。

提示

Chap 04 栈，习题 4-4

Chap 06 二叉搜索树，习题 7-2

卡特兰数的公式为：$\mathrm{Catalan}(n)=\dfrac{(2n)!}{(n+1)!n!}$，具体的推导方法见教材。

一般我们会在以下场景看到卡特兰数的应用：

• 二叉树的不同结构数
• 互异关键码构成的二叉搜索树个数
• 互异数的合法栈混洗序列个数
• 若干对括号的合法括号配对个数
• 其他本质相同的建模

请注意，本题如果直接计算 $(2n)!$ 会超出 long long 甚至 __int128 的表示范围，可以考虑使用高精度乘/除低精度，或者更换计算顺序来进行有效计算。