题目描述

给定一棵含有 $N$ 个节点的平衡二叉树，求有多少种形态的平衡二叉树恰好有$N$个节点。

平衡二叉树是一颗具有下列性质的二叉树：

• 根结点的左右子树高度之差不超过 $1$
• 每个子树也是构成平衡二叉树

由于答案可能比较大，输出总方案数模 $1,000,000,007$ 的余数。

输入格式

• 单个整数：表示 $N$

输出格式

• 单个整数：表示答案。

10

60

数据范围

• $30\%$ 的数据，$1\leq N\leq 10$
• $100\%$ 的数据，$1\leq N\leq 5000$