题目描述

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

输入格式

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

输出格式

输出答案mod 1e9+7的结果。

样例输入1

2
3
4
5

样例输出1

2
1
4
6

样例解释

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