Problem Background

On a warm summer night, Vito and his good friend Karlo are lying on a clearing in the forest, gazing at the stars. Suddenly, Vito exclaims, "Karlo, look! The trees around us are changing colors!" "Wow, what a riot of colors!" Karlo exclaims in amazement. Indeed, the branches in the forest are starting to change colors.

Problem Description

Vito and Karlo are captivated by these colorful trees, and they also notice something else. Each tree they are observing can be considered as a tree graph, i.e., an undirected graph where there is exactly one path between any two points. Each tree they are observing has this characteristic: each edge is colored in one of $k$ colors. A path on the tree is considered colorful if it contains at least two edges of different colors.

By morning, the magic of the trees has vanished. Vito and Karlo remember the starting and ending points of $m$ colorful paths. They wonder: how many possible trees satisfy the conditions? Since the answer could be very large, please output the answer modulo $10^9+7$.

Input Format

The first line contains three integers $n, m, k$, representing the number of nodes in the tree, the number of colorful paths that Vito and Karlo remember, and the total number of colors for the branches.

The next $n-1$ lines, the $i+1$-th line contains two integers $a_i, b_i$, indicating that there is a tree edge between node $a_i$ and node $b_i$.

The next $m$ lines, the $n+j$-th line contains two integers $c_j, d_j$, indicating that there is a colorful path from node $c_j$ to node $d_j$. It is guaranteed that $c_j$ and $d_j$ are not adjacent.

Output Format

Output a single line, the number of possible trees that satisfy the conditions, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

3 1 2
1 2
2 3
1 3

Sample Output #1

2

Sample Input #2

4 3 2
1 2
2 3
4 2
1 4
1 3
4 3

Sample Output #2

0

Sample Input #3

4 3 3
1 2
2 3
4 2
1 4
1 3
4 3

Sample Output #3

6

Notes

[Sample 1 Explanation]

The first scenario is where the edge between node $1$ and node $2$ is colored $1$, and the edge between node $2$ and node $3$ is colored $2$.

The second scenario is where the edge between node $1$ and node $2$ is colored $2$, and the edge between node $2$ and node $3$ is colored $1$.

[Data Range and Constraints]

This problem uses subtask-based scoring.

• Subtask 1 (10 pts): $m = 1$.
• Subtask 2 (15 pts): $m = 2$.
• Subtask 3 (10 pts): Each tree edge belongs to at most one of the $m$ colorful paths.
• Subtask 4 (10 pts): $1 ≤ n ≤ 15, k = 2$.
• Subtask 5 (65 pts): No additional constraints.

For $100\%$ of the data, $3 ≤ a_i, b_i, c_j, d_j ≤ n ≤ 60, 1 ≤ m ≤ 15, 2 ≤ k ≤ 10^9$.

[Hint and Attribution]

This problem is scored according to the original COCI settings, with a full score of $110$.

The problem is translated from COCI2021-2022 CONTEST #4 T5 Šarenlist.

见题面 Input 部分

见题面 Output 部分