圣主的考验
时间限制：10s 空间限制：128MB
题目描述
若对于二叉树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