题目描述

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 \ne 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
3 6 2
1 2
1 3
1 1
2 2
3 3
1 2
1 3
2 3

10

提示

翻译由 DeepSeek V4 Pro 完成