AZY的看图数数

题目描述

AZY童鞋很喜欢有美感的艺术设计，有一天他看到了这样一种由圆形和线段构成的图案。 显然，上图中有15个节点（圆形）。除了最底下的绿色节点，每个节点都有两个“下属节点”。

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

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

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

当n = 4,5,6...时呢？不同结构的图案数一共多少？

输入

多组测试数据，输入节点数n，0<=n<20

输出

对于每组数据（即每个n），输出一行，为对应的不同图案的个数。

输入样例

1

输出样例

1

Hint

• 如果没有节点，那就认为没有图案。
• 当n = 15的时候，答案的值接近一千万。
• 本题和数据结构的存储结构什么的完全无关。
• 水水哒AZY助教出的题一般都很温和的请大家放心（其实是因为自己不会难题）。