Balanced Binary Tree

Problem Description

A balanced binary tree (AVL tree) is a binary tree in which the height difference between the left and right subtrees is at most $1$, and both the left and right subtrees are themselves AVL trees. Given the number of nodes $n$, count how many distinct AVL tree shapes have exactly $n$ nodes.

Input Format

One line containing an integer $T$ ($T \le 2000$), the number of test cases.

The next $T$ lines each contain an integer $n$ ($n \le 2000$).

Output Format

For each test case, output one number — the result. Since the result may be huge, output it modulo $10^9 + 7$.

Sample Input

1
10

Sample Output

60