题意转化与核心观察

把树按根 1 定向为有根树，则任意节点必须在其父亲被感染之后才有可能被感染——这是唯一约束：

• 必要：若子节点先于父节点被感染会与“新增节点需与已感染连通块相邻”矛盾。
• 充分：若一节点的父亲已感染，那么该节点必定有一条与感染块相邻的边（父边），因此可在任意一天选择它被感染。

于是问题等价于：把除根以外的 $n-1$ 个节点排成一个线性序，使得每个节点都在其父节点之后出现。这正是以父子关系为偏序的线性扩展数。

算法思路（树形 DP + 多项式合并/多重组合数）

题目内容

给定一棵含 $n$ 个节点、根节点为 $1$ 的无向树，每个节点最开始均为健康。第 $0$ 天，根节点 $1$ 被感染。

此后，每天感染会向当前任意一个已感染节点的一个健康邻居节点蔓延。可以证明，经过 $k$ 天后，恰有 $k+1$ 个节点被感染，且构成一棵以 $1$ 为根的连通子树。

请计算恰好在 $n-1$ 天内感染整棵树的不同感染过程方案数。由于答案可能很大，请将结果对 $10^9+7$ 取模后输出。

具体地，定义长度为 $n-1$ 的二元组序列 $s_1,s_2,...,s_{n-1}$ ，其中第 $i$ 个二元组 $s_i$ 代表选择感染了边 $(u_i,v_i)$ ，要求 $u_i$ 已在前 $i-1$ 天被感染， $v_i$ 当天被新感染。统计所有可能的二元组序列的数量。两个感染方案不同即等价于两个二元组序列不同。

输入描述

第一行输入一个整数 $T(1≤T≤10)$ ，代表测试用例数。

接下来每组测试数据格式如下：

• 第一行输入一个整数 $n(1≤n≤2×10^5)$ ，表示树的节点数；
• 接下来 $n-1$ 行，每行输入两个整数 $u,v(1≤u,v≤n)$ ，表示一条无向边。

所有测试用例中 $\sum n≤2×10^5$ 。

输出描述

对于每个测试用例，在一行输出一个整数，表示感染整棵树的方案数。由于答案可能很大，请将结果对 $10^9+7$ 取模后输出。

样例1

输入

2
3
1 2
2 3
4
1 2
1 3
1 4

输出

1
6

说明

第一组：链型树 $1-2-3$ ，只能依次感染 $2$ 再 $3$ ，共 $1$ 种；

第二组：星型树 $1-${$2,3,4$} ，可任意顺序感染三颗子节点，方案数 $3!=6$ 。