若对于二叉树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。
BZPRO