Yousef 有一个有根树$$$^{\text{*}}$$$,由 $$$n$$$ 个顶点组成,根位于顶点 $$$1$$$。您想给 Yousef 一个长度为 $$$n$$$ 的数组 $$$a$$$,其中每个 $$$a_i$$$ $$$(1 \le i \le n)$$$ 可以是 $$$1$$$ 或 $$$2$$$.
设 $$$s_u$$$ 表示 $$$a_v$$$ 的总和,其中顶点 $$$v$$$ 位于顶点 $$$u$$$ 的子树 $$$^{\text{†}}$$$ 中。尤瑟夫思考着这棵树 特别 如果 $$$s$$$ 中的所有值都是 成对不同 (即所有子树总和都是唯一的)。
你的任务是帮助 Yousef 计算不同数组 $$$a$$$ 的数量,这些数组导致树被 特别。如果存在索引 $$$i$$$ 使得 $$$b_i \neq c_i$$$,则两个数组 $$$b$$$ 和 $$$c$$$ 不同。
由于结果可能非常大,您应该打印它对 $$$10^9 + 7$$$ 取模。
$$$^{\text{*}}$$$树是具有 $$$n - 1$$$ 边的连通无向图。
$$$^{\text{†}}$$$顶点 $$$v$$$ 的子树是在到根的简单路径上经过 $$$v$$$ 的所有顶点的集合。请注意,顶点 $$$v$$$ 也包含在集合中。
输入
第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。
每个测试用例由几行组成。测试用例的第一行包含一个整数 $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$ — 树中的顶点数。
接下来是 $$$n−1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ $$$(1 \le u,v \le n, u \ne v)$$$ 描述由一条边连接的一对顶点。保证给定的图是一棵树并且没有循环或多重边。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 $$$x$$$ — 导致树为以下形式的不同数组 $$$a$$$ 的数量 特别,模 $$$10^9 + 7$$$。
示例
输入复制
721 281 22 33 82 44 55 66 7101 22 33 44 55 64 77 84 99 1071 44 23 23 52 66 771 22 33 43 54 66 775 74 61 61 32 66 753 41 21 32 5
输出复制
4 24 0 16 48 0 4
注意
第五个测试用例中给出的树: