Perfect Binary Trees
**Note: The memory limit for this problem is 512MB, twice the default.**
A perfect binary tree is a rooted tree where every non-leaf node has exactly two children and all leaf nodes are at an equal distance from the root.
An unrooted perfect binary tree is an unrooted tree that is a perfect binary tree when rooted at one of its nodes.
Bessie has a tree with N (1≤N≤105) nodes. Determine the number of ways to remove a subset of edges from the tree so that the resulting forest is a collection of unrooted perfect binary trees. As the answer may be very large, output the result modulo 109+7.
In the first test case, Bessie can remove any of the following subsets of edges to get a forest of perfect binary trees:
- (2,6)
- (1,2), (2,3), (2,6)
- (1,2), (2,3), (4,6)
- (1,2), (2,3), (5,6)
- (1,2), (4,6), (5,6)
- (2,6), (4,6), (5,6)
- (2,3), (4,6), (5,6)
- (1,2), (2,3), (2,6), (4,6), (5,6)
The first subset results in two subtrees of height 1, the last subset results in six subtrees of height 0, and the other subsets result in three subtrees of height 0 and one subtree of height 1.
SCORING:
- Inputs 2-3: N≤15
- Inputs 4-5: No node is adjacent to more than two other nodes.
- Inputs 6-9: N≤1000, the sum of N does not exceed 2000, and no node is adjacent to more than three other nodes.
- Inputs 10-13: No node is adjacent to more than three other nodes.
- Inputs 14-21: No additional constraints.
Problem credits: Avnith Vijayram
Source: USA Computing Olympiad.
Input Format
The first line contains an integer T (1≤T≤100), the number of independent test cases.
The first line of each test case contains an integer N.
Each of the next N−1 lines of each test case contains two integers ui and vi (1≤ui,vi≤N) indicating an edge between nodes ui and vi .
It is guaranteed that for each test case, the given edges form a tree with N nodes.
Additionally, the sum of N over all test cases does not exceed 2⋅105.
Output Format
For each test case, output a single integer: the number of subsets of edges that, when removed, result in a forest that is a collection of unrooted perfect binary trees, modulo 109+7.