题目描述

若对于二叉树T的每个节点v，其左子树的高度L和右子树的高度R均满足|L – R|≤1，则这个树T有可能来自超自然之界。规定若某节点子树为空，则该子树的高度是0。你的任务是求有N个节点的可能来自超自然之界的树的数目。

输入格式

每个测试点包含若干个测试数据。 每个测试数据占一行，包含一个整数N。 输入文件以0结尾。

输出格式

对于每个测试数据，在单独的一行内输出结果。由于结果可能会很大，你只需要输出答案在十进制表示下的后九位。若答案不足九位，只需输出原答案。

2
3
5
30
0

2
1
6
11307920

提示

对于100% 的测试点，1≤N≤3000。

题目来源

Poetize11