题目描述

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