题目描述

注意：本题的内存限制为 $512$MB，是默认限制的两倍。

完美二叉树 是一棵有根树，其中每个非叶结点恰好有两个孩子，且所有叶子结点到根的距离相等。

无根完美二叉树 是一棵无根树，当以它的某个结点为根时，它是一棵完美二叉树。

Bessie 有一棵包含 $N$（$1 \le N \le 10^5$）个结点的树。请计算有多少种删除树中边集的方法，使得得到的森林是由若干棵无根完美二叉树构成的集合。由于答案可能很大，请输出对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 100$），表示独立测试用例的数量。

每个测试用例的第一行包含一个整数 $N$。

接下来每个测试用例的 $N - 1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le N$），表示结点 $u_i$ 与 $v_i$ 之间的一条边。

保证对于每个测试用例，给出的边构成一棵包含 $N$ 个结点的树。

此外，所有测试用例的 $N$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数：删除边集后，得到的森林是由无根完美二叉树构成的集合的方案数，对 $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

提示

在第一个测试用例中，Bessie 可以删除以下任意边集，使得得到的森林由完美二叉树构成：

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)$

第一个边集得到两棵高度为 $1$ 的子树，最后一个边集得到六棵高度为 $0$ 的子树，其余边集得到三棵高度为 $0$ 的子树和一棵高度为 $1$ 的子树。

计分规则

• 输入 $2$-$3$：$N \le 15$
• 输入 $4$-$5$：没有结点的度数超过 $2$。
• 输入 $6$-$9$：$N \le 1000$，所有测试用例的 $N$ 之和不超过 $2000$，且没有结点的度数超过 $3$。
• 输入 $10$-$13$：没有结点的度数超过 $3$。
• 输入 $14$-$21$：无额外限制。

翻译由 DeepSeek V4 Pro 完成