平衡二叉树

题目描述

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

输入格式

一行一个整数$T(T\leq 2000)$表示数据组数

T行, 每行一个整数$n(n\leq 2000)$

输出格式

每行一个数字表示结果，由于结果巨大，输出它对$10^9 + 7$取余数的结果。

样例输入

1
10

样例输出

60