## CODEIT01 - TREE SHAPES

**TREE SHAPES**

**Problem Statement:**

Given n, the number of nodes, find the number of different possible binary trees that can be constructed. A tree differs from another tree if it’s shape looks different.

**Input Specification:**

The first line is an integer t, denoting the number of test cases. Then each test case consists of one integer n, the number of nodes.

**Output Specification:**

For each test case print the number of possible trees that can be constructed using n nodes in a separate line.

Print the answer mod 10^9+7.

**Input Constraints:**

**1<=t<=100**

**1<=**n**<=50**

**Sample Input:**

4 1 2 3 4

Sample Output:

1 2 5 14

Added by: | cegprakash |

Date: | 2012-01-09 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 GOSU |