1219 - Balance Binary Search Tree

Time Limit: 2s Memory Limit: 128MB

Submissions: 149 Solved: 19
Description
A Balance Binary Search Tree(BBST) is a kind of Binary Search Tree(BST) that the depth's difference of its left and right sub-tree is no more than 1. Now I want to ask you the number of different shaped BBST`s with N nodes. Maybe the number is too large, you should only tell me the number of all the different shapes of BBST mod 2007, which is much easier.
Input
The first line of the input is a positive integer T(1<=T<=1000), denoting the number of test cases followed. For each test case, there is an Integer N(0<=N<=250), denoting the number of node the tree has.
Output
For each test case, you should output the answer, one for a line.
Sample Input
2
1
2
Sample Output
1
2
Hint
Source
Sempr, HUST Programming Contest 2007