**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.
INPUT FORMAT (input arrives from the terminal / stdin):
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 (print output to the terminal / stdout):
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.
SAMPLE INPUT:
3
6
1 2
3 2
4 6
5 6
6 2
3
1 2
3 2
7
2 1
2 3
1 6
1 7
3 4
3 5
SAMPLE OUTPUT:
8
2
14
In the first test case, Bessie can remove any of the following subsets of edges to get a forest of perfect binary trees:
1.(2,6)(2,6)
2.(1,2)(1,2), (2,3)(2,3), (2,6)(2,6)
3.(1,2)(1,2), (2,3)(2,3), (4,6)(4,6)
4.(1,2)(1,2), (2,3)(2,3), (5,6)(5,6)
5.(1,2)(1,2), (4,6)(4,6), (5,6)(5,6)
6.(2,6)(2,6), (4,6)(4,6), (5,6)(5,6)
7.(2,3)(2,3), (4,6)(4,6), (5,6)(5,6)
8.(1,2)(1,2), (2,3)(2,3), (2,6)(2,6), (4,6)(4,6), (5,6)(5,6)
The first subset results in two subtrees of height 11, the last subset results in six subtrees of height 00, and the other subsets result in three subtrees of height 00 and one subtree of height 11.
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 20002000, 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
