P17424 [ICPC 2018 Xuzhou R] Rikka with Intersections of Paths

Rikka has a tree $T$ with $n$ vertices numbered from $1$ to $n$. Meanwhile, Rikka has marked $m$ simple paths in $T$, the $i$-th of which is between the vertices $x_i$ and $y_i$, where some of them could be the same path. Now, Rikka wants to know in how many different strategies she can select $k$ paths from the marked paths such that those selected paths share at least one common vertex.

The input contains several test cases, and the first line contains a single integer $T$ ($1 \le T \le 200$), the number of test cases. For each test case, the first line contains three integers $n$ ($1 \le n \le 3 \times 10^5$), the size of the tree $T$, $m$ ($2 \le m \le 3 \times 10^5$), the number of marked paths, and $k$ ($2 \le k \le m$). The following $(n - 1)$ lines describe the tree $T$. Each of them contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$), representing an edge between the vertices $u$ and $v$. The following $m$ lines describe all marked simple paths in the tree. The $i$-th of them contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$). The input guarantees that the sum of $n$ and the sum of $m$ in all test cases are at most $2 \times 10^6$ respectively.

For each test case, output a single line with a single integer, the number of different strategies meeting the requirement modulo $(10^9 + 7)$.