题目描述

Note: The memory limit for this problem is $512$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 $N$ ($1 \le N \le 10^5$) 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 $10^9 + 7$.

输入格式

The first line contains an integer $T$ ($1 \le T \le 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 $u_i$ and $v_i$ ($1 \le u_i, v_i \le N$) indicating an edge between nodes $u_i$ and $v_i$.

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 \cdot 10^5$.

输出格式

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 $10^9 + 7$.

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

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. $(1, 2), (2, 3), (2, 6)$
3. $(1, 2), (2, 3), (4, 6)$
4. $(1, 2), (2, 3), (5, 6)$
5. $(1, 2), (4, 6), (5, 6)$
6. $(2, 6), (4, 6), (5, 6)$
7. $(2, 3), (4, 6), (5, 6)$
8. $(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 \le 15$
• Inputs $4$-$5$: No node is adjacent to more than two other nodes.
• Inputs $6$-$9$: $N \le 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.