405617: GYM102012 G 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)$$$.

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

10