#216608. [USACO26OPEN] Perfect Binary Trees

Note: The memory limit for this problem is MB, 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 () 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 .

The first line contains an integer (), the number of independent test cases.

The first line of each test case contains an integer .

Each of the next lines of each test case contains two integers and () indicating an edge between nodes and .

It is guaranteed that for each test case, the given edges form a tree with nodes.

Additionally, the sum of over all test cases does not exceed .

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 .

样例输入 1

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

样例输出 1

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:

The first subset results in two subtrees of height , the last subset results in six subtrees of height , and the other subsets result in three subtrees of height and one subtree of height .

SCORING

• Inputs -:
• Inputs -: No node is adjacent to more than two other nodes.
• Inputs -: , the sum of does not exceed , and no node is adjacent to more than three other nodes.
• Inputs -: No node is adjacent to more than three other nodes.
• Inputs -: No additional constraints.