A. [百度之星 2025] Bus Station

有一棵 个节点的树。令 表示树上 两点之间的简单路径 † 。称一个树上所有简单路径组成的集合 ⋆ 的子集 是好的，当且仅当：

• 树上每条边 都被 恰好一条 中的路径覆盖 ‡ 。

对于一个好的集合 ，设 表示对所有 ，结点 在 中作为某条路径端点的出现次数的最大值。形式化地，

你需要统计有多少个好的集合 满足 取到 （即所有好的集合 中 的最小值），答案对 取模。

† ：一条路径是简单路径，当且仅当其不重复经过任何结点。树上任意两个结点 之间有且仅有一条简单路径。
⋆ ：树上所有简单路径组成的集合，可以看做对每个 的节点对 ， 组成的集合。
‡ ：称边 被简单路径 覆盖，当且仅当点 均在 的简单路径上。

本题单个测试点内有多组测试数据。
第一行，一个整数 （），描述数据组数。对于每组数据：

• 第一行，一个整数 （），表示树中的结点数。
• 接下来 行，每行两个整数 和 （），表示一条在结点 和结点 之间的连边。

保证给出的所有边构成一棵树；保证对单个测试点，所有 的和不超过 。

对于每组数据，输出一行一个整数，表示好的集合 中，满足 取到其能够取到的最小值的集合数量，答案对 取模。

样例 1

输入：

3
3
1 2
2 3
7
1 4
5 3
2 4
1 6
4 3
3 7
10
1 5
5 2
2 10
5 8
1 4
5 6
4 3
2 7
9 5

输出：

1
9
45

样例解释：
对于第一组数据，好的集合 共有两个：

• ；
• 。

因为 （结点 都出现了 次），而 （结点 出现了 次），因此只有 是好的，答案为 。