#3057. 圣主的考验

内存限制:128 MiB 时间限制:10 Sec

题目描述

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