题目描述

平衡二叉树（AVL树），是指左右子树高度差至多为 $1$ 的二叉树，并且该树的左右两个子树也均为 AVL 树。 现在问题来了，给定 AVL 树的节点个数 $n$，求有多少种形态的 AVL 树恰好有 $n$ 个节点。

输入格式

输入就一个参数$n(1\leq n \leq 2000)$

输出格式

输出答案 $\bmod 10^9+7$ 的结果。

样例输入1

2
3
4
5

样例输出1

2
1
4
6

样例解释

没有解释就是最好的解释。