trouble-with-trees

2)  Krishna had just completed his class on trees. To make things worse , the teacher had asked them to draw all possible ‘Binary Trees’ as an assignment . After persistent requests, the teacher relaxed the assignment by asking them to tell the number of trees possible given the number of keys. Krishna started of his assignment in excitement but soon realized that the assignment was in no way easier than before when he saw large ‘n’ values. Can you help Krishna with his assignment ?
Output the answer mod 1e9+7
Input
t- no of testcases
n- no of keys

Constraints:
1 ≤ t ≤ 50
1 ≤ n ≤ 1000

SAMPLE INPUT
4
1
2
3
4

SAMPLE OUTPUT
1
2
5
14

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: