Rikka 拥有一棵包含 $n$ 个顶点的树 $T$，顶点编号从 $1$ 到 $n$。 同时，Rikka 在 $T$ 中标记了 $m$ 条简单路径，其中第 $i$ 条路径连接顶点 $x_i$ 和 $y_i$，这些路径中可能存在相同的路径。 现在，Rikka 想知道她有多少种不同的策略可以从这些标记的路径中选择 $k$ 条路径，使得这些被选中的路径至少共享一个公共顶点。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 200$)，表示测试用例的数量。 对于每个测试用例，第一行包含三个整数 $n$ ($1 \le n \le 3 \times 10^5$)，表示树 $T$ 的大小；$m$ ($2 \le m \le 3 \times 10^5$)，表示标记路径的数量；以及 $k$ ($2 \le k \le m$)。 接下来的 $(n - 1)$ 行描述了树 $T$。每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示顶点 $u$ 和 $v$ 之间的一条边。 接下来的 $m$ 行描述了树中所有的标记简单路径。第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le n$)。 输入保证所有测试用例中 $n$ 的总和与 $m$ 的总和分别不超过 $2 \times 10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示满足要求的不同策略数量，结果对 $(10^9 + 7)$ 取模。

样例

样例输入 1

1
3 6 2
1 2
1 3
1 1
2 2
3 3
1 2
1 3
2 3

样例输出 1

10