UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3057. 圣主的考验

Statistics 下载数据

Description

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

Input

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

Output


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

Sample Input

2
3
5
30
0


Sample Output


2
1
6
11307920

Hint


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

Source

Poetize11