Busy Beaver 又在农贸市场制造混乱了！这一次，他在各个摊位之间发起了一场食物大战。

摊位编号从 $1$ 到 $N$，由 $N - 1$ 条道路连接，形成一棵树。换句话说，可以通过道路从任意一个摊位到达另一个摊位，且任意两个摊位之间有且仅有一条简单路径。

Busy Beaver 按以下规则将每个摊位分配给“土豆队”（Team Potato）或“番茄队”（Team Tomato）：

• 他从摊位 $1$ 出发，沿着道路行走，访问每一个摊位，最后回到摊位 $1$。在所有此类路线中，他选择一条总路程最短的路线。
• 摊位 $1$ 被分配给土豆队。
• 每当 Busy Beaver 第一次访问一个摊位（摊位 $1$ 除外）时，他会立即将其分配给两个队伍中的一个。为了保持公平，他每次分配新摊位时都会交替分配队伍。也就是说，如果最近分配的摊位属于土豆队，那么下一个新访问的摊位必须分配给番茄队，反之亦然。

你的任务是计算可能的队伍分配方案数。注意，不同的最短路线可能会产生相同的最终分配结果；此类分配方案应仅计数一次。由于答案可能非常巨大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。 每个测试用例的第一行包含一个整数 $N$ ($2 \le N \le 10^5$)。 接下来的 $N - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le N, u \neq v$)，表示摊位 $u$ 和 $v$ 之间有一条道路。 所有测试用例的 $N$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数：可能的最终队伍分配方案数，对 $10^9 + 7$ 取模。

子任务

本题有两个子任务：

• (10 分)：摊位构成一棵以摊位 $1$ 为根的星形图。具体来说，摊位 $1$ 连接了 $N - 1$ 条道路。
• (20 分)：摊位构成一棵以摊位 $1$ 为根的二叉树。具体来说，摊位 $1$ 最多连接 $2$ 条道路，其他每个摊位最多连接 $3$ 条道路。
• (70 分)：无附加限制。

样例

样例输入 1

4
4
1 2
2 3
2 4
7
1 2
1 3
1 4
1 5
1 6
1 7
7
1 2
1 3
2 4
2 5
3 6
3 7
7
1 2
1 3
1 4
2 5
2 6
2 7

样例输出 1

2
20
8
12

说明

样例包含 $4$ 个测试用例：

• 测试用例 $1$ 满足第二个子任务（二叉树）。
• 测试用例 $2$ 满足第一个子任务（星形图）。
• 测试用例 $3$ 满足第二个子任务（二叉树）。
• 测试用例 $4$ 满足第三个子任务（无附加限制）。

在第一个测试用例中，一种可能的队伍分配方案如下所示。

一条最短路线为： $1 \to 2 \to 3 \to 2 \to 4 \to 2 \to 1$。

其总长度为 $6$，这是从摊位 $1$ 出发、访问所有摊位并回到摊位 $1$ 的路线中可能的最短长度。

摊位按照首次访问的顺序进行分配： 摊位 $1$ 分配给土豆队。 摊位 $2$ 分配给番茄队。 摊位 $3$ 分配给土豆队。 摊位 $4$ 分配给番茄队。

另一种可能的队伍分配方案是通过在访问摊位 $3$ 之前访问摊位 $4$ 获得的，这会交换它们的队伍。因此，可能的队伍分配方案总数为 $2$。