SP11905 TRECOUNT - Tree Count

我们的超级英雄 Carry Adder 揭开了邪恶角色 Head Crash 用来生成他位于奥克兰堡垒入口代码的秘密方法。这个代码实际上是拥有特定属性的不同二叉搜索树的数量。为了保证代码不太长，Head Crash 只取它的最低九位数字。 这种二叉搜索树的特定属性是：对于树中的每个节点，其右子树的高度与左子树的高度之差不超过 1。这里，子树的高度定义为从该子树的根节点到任意一个叶节点的最长路径的长度。值得注意的是，一个仅包含一个节点的子树高度为 0，而空树则规定其高度为 -1。

输入由若干行组成。每一行代表一个测试用例，只包含一个整数 $N$，表示节点的数量，$N$ 的范围包括从 $1$ 到 $1427$。

对于每个测试用例，输出一个九位数的代码（注意输出时要保留前导零）。 **本翻译由 AI 自动生成**