题目描述

小 Q 是一个算法竞赛初学者，正在学习图论知识中的树的遍历。一棵由 $n$ 个结点，$n − 1$ 条边构成的树，初始时所有结点都未被标记，它的遍历过程如下：

1. 选择一个结点 $s$ 作为遍历起始结点，并把该结点打上标记。
2. 假设当前访问的结点为 $u$，寻找任意一个与 $u$ 相邻且未标记的结点 $v$，将 $v$ 作为新的当前访问结点并打上标记。之后再次进入第 2 步。
3. 假设在第 2 步中，与 $u$ 相邻的结点都已被标记，如果 $u = s$ 则遍历过程结束，否则将 $u$ 设为遍历 $u$ 之前的上一个结点并再进入第 2 步。 例如在下面的树中，一种可能的遍历过程如下： • 选取 $1$ 作为遍历起始结点，并把 $1$ 打上标记； • $2$ 与 $1$ 相邻且未标记，将 $2$ 设为当前访问结点，并把 $2$ 打上标记。 • $2$ 与 $3$ 相邻且未标记，将 $3$ 设为当前访问结点，并把 $3$ 打上标记。 • $3$ 所有相邻的结点都被标记，将当前访问结点设为遍历结点 $3$ 之前的结点 $2$。 • $2$ 与 $4$ 相邻且未标记，将 $4$ 设为当前访问结点，并把 $4$ 打上标记。 • $4$ 所有相邻的结点都被标记，将当前访问结点设为遍历结点 $4$ 之前的结点 $2$。 • $2$ 所有相邻的结点都被标记，将当前访问结点设为遍历结点 $2$ 之前的结点 $1$。 • $1$ 所有相邻的结点都被标记，且 $1$ 是遍历起始结点，故遍历结束。 作为一个奇思妙想的学生，小 Q 在学习完上述知识后不满足于以结点为基础的遍历方式，于是开始研究以边为基础的遍历方式。定义两条边相邻，当且仅当它们有一个公共的结点。初始时，所有的边都未被标记。这种以边为基础的遍历过程如下：
4. 选择一条边 $b$ 作为遍历起始边，并把该边打上标记。
5. 假设当前访问边为$e$ ，寻找任意一条与 $e$ 相邻且未标记的边 $f$，将 $f$ 作为新的当前访问边并打上标记。之后再次进入第 2 步。
6. 假设在第 2 步中，与 $e$ 相邻的边都已被标记，如果 $e = b$ 则遍历过程结束，否则将 $e$ 设为遍历 $e$ 之前的上一条边并再进入第 2 步。 例如在上面的树中，一种可能的遍历过程如下（定义 {$u$, $v$} 表示连接结点 $u$ 和 $v$ 的边）： • 选取 {1, 2} 作为遍历起始边，并把 {1, 2} 打上标记； • {$1$, $2$} 与 {$2$, $3$} 相邻且未标记，将 {$2$, $3$} 设为当前访问边，并把 {$2$, $3$} 打上标记。 • {$2$, $3$} 与 {$2$, $4$} 相邻且未标记，将 {$2$, $4$} 设为当前访问边，并把 {$2$, $4$} 打上标记。 • {$2$, $4$} 所有相邻的边都被标记，将当前访问边设为遍历 {$2$, $4$} 之前的边 {$2$, $3$}。 • {$2$, $3$} 所有相邻的边都被标记，将当前访问边设为遍历 {$2$, $3$} 之前的边 {$1$, $2$}。 • {$1$, $2$} 所有相邻的边都被标记，且 {$1$, $2$} 是遍历起始边，故遍历结束。 小 Q 惊奇的发现，在这个新的树的遍历过程中，如果将每条边看作一个新的结点，将步骤 2 中的所有新结点 $e$ 和 $f$ 连接一条新边，就会生成一棵由 $n−1$ 个新结点和 $n−2$条新边连接成的新树。例如上述遍历过程得到的新树如下（新的结点和新边都用红色表示）： 现在小 Q 在 $n − 1$ 条边中选择了 $k$ 条关键边。小 Q 想知道，以任意一条关键边作为起始遍历边，通过上述遍历过程能够生成多少种不同的新树。这里两棵树被认为是不同的，当且仅当至少存在某一对新的结点，它们仅在其中一棵树中连有新边。 由于结果可能很大，你只需要输出其对$10^9 + 7$ 取模的结果即可。

输入

本题有多组测试数据。 输入的第一行包含两个整数 $c$, $T$，表示测试点的编号和测试数据的组数。在样例中，$c$ 表示该样例与测试点 $c$ 的数据范围相同。 接下来包含 $T$ 组数据，每组数据的格式如下： • 第一行包含两个整数 $n$, $k$，表示树的结点数以及小 Q 选择的关键边的数量。 • 接下来 $n − 1$ 行，第 $i$ 行包含两个整数 $u_i$, $v_i$，表示树上编号为 $i$ 的边连接结点$u_i$ 和 $v_i$。 • 接下来一行包含 $k$ 个整数 $e_1$, $e_2$, . . . ,$e_k$，表示小 Q 选择的关键边的编号。保证关键边的编号互不相同。

输出

对于每组测试数据输出一行，包含一个整数，表示结果对 $10^9 + 7$ 取模的结果。

输入样例

1 1
4 1
1 2
2 3
2 4
1

输出样例

2

提示

【样例 1 解释】 两种可能的新树如下： • 新结点 {$1$, $2$} 和新结点 {$2$, $3$} 连新边，新结点 {$2$, $3$} 和新结点 {$2$, $4$} 连新边。 • 新结点 {$1$, $2$} 和新结点 {$2$, $4$} 连新边，新结点 {$2$, $4$} 和新结点 {$2$, $3$} 连新边。 【样例 2 输入】

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

【样例 2 输出】

3

【样例 2 解释】 三种可能的新树如下： • 新结点 {$1$, $2$} 和 {$1$, $3$}，{$1$, $2$} 和 {$2$, $4$}，{$2$, $4$} 和 {$2$, $5$} 之间分别连新边。该新树可以选择 {$1$, $2$} 作为起始遍历边得到。 • 新结点 {$1$, $2$} 和 {$1$, $3$}，{$1$, $2$} 和 {$2$, $5$}，{$2$, $5$} 和 {$2$, $4$} 之间分别连新边。该新树可以选择 {$1$, $2$} 或 {$2$, $4$} 作为起始遍历边得到。 • 新结点 {$1$, $2$} 和 {$1$, $3$}，{$1$, $2$} 和 {$2$, $4$}，{$1$, $2$} 和 {$2$, $5$} 之间分别连新边。该新树可以选择 {$2$, $4$} 作为起始遍历边得到。 【数据范围】 对于所有的测试数据，保证： • $1 ≤ T ≤ 10$； • $2 ≤ n ≤ 10^5$； • $1 ≤ k < n$； • 对于任意的 $i$($1 ≤ i ≤ n − 1$)，都有 $1 ≤ u_i, v_i ≤ n$，且构成一颗合法的树。 • 对于任意的 $i$($1 ≤ i ≤ k$)，都有 $1 ≤ e_i < n$，且两两不同。

测试点	n	k	特殊性质
1 ∼ 3	≤ 5	≤ 1	无
4 ∼ 6	≤ 105
7 ∼ 10		≤ 2
11, 12	≤ 500	≤ 8
13, 14	≤ 102	< n
15	≤ 500
16, 17	≤ 105	≤ 500
18		< n	A
19 ∼ 21			B
22, 23	≤ 2 × 104		无
24, 25	≤ 105

• 特殊性质 A：对于任意的 $i$($1 ≤ i ≤ n − 1$)，都有 $u_i = i$, $v_i = i + 1$。 • 特殊性质 B：对于任意的 $i$($1 ≤ i ≤ n − 1$)，都有 $u_i = 1$, $v_i = i + 1$。 【提示】 数据输入的规模可能较大，请选手注意输入读取方式的效率。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共7个测试点，非原站或官方原始数据。总分100分。