Give Me Back My Binary Tree!!!
Time limit2sMemory limit1024 MB
Count the number of distinct binary trees with exactly E edges, where mirror images count as different trees, modulo 1e9+7.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Combinatorics, Math, Tree
- Solved
- No attempts yet
Problem
A binary tree is a tree in which each node has at most two child nodes.
Chisam had a binary tree that was connected infinitely. But while he slept through the night, someone separated all the vertices and edges of Chisam's binary tree and then stole every edge except E of them. Now Chisam has nothing left but infinitely many vertices and E edges. Chisam wants to rebuild a single binary tree using those E edges. To build the binary tree, he must use all E edges to connect the vertices, and he discards the vertices left over after the binary tree is complete.
Two trees that are symmetric to each other count as different cases. Help Chisam find the number of binary trees he can build with E edges.
Input
The first line gives T(1 ≤ T ≤ 100), the number of test cases.
From the second line on, each test case gives E, the number of edges. (1 ≤ E ≤ 5,000)
Output
For each test case, print the number of binary trees modulo 1,000,000,007.