圣主的考验

时间限制: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