题目描述

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

输入格式

每个测试点包含若干个测试数据。

每个测试数据占一行，包含一个整数 $\red{N}$。 输入文件以 $\red{0 }$结尾。

输出格式

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

样例

输入样例

2
3
5
30
0

输出样例

2
1
6
11307920

提示

对于 $\red{30\% }$的测试点，$\red{N≤}$$\red{100}$。

对于 $\red{70\% }$的测试点，$\red{N≤}$$\red{1000}$。

对于 $\red{100\% }$的测试点，$\red{1≤}$$\red{N≤}$$\red{3000}$。