Background

On a warm summer night, Vito and his good friend Karlo lay on a forest clearing watching the stars. Suddenly, Vito shouted, “Karlo, look. All the trees around us are changing color.” “Wow, so colorful.” Karlo said in surprise. Indeed, the branches in the forest started changing color.

Problem Description

Vito and Karlo were fascinated by these colorful trees, and they also noticed a few things. Each tree they are watching can be seen as a tree graph, i.e., an undirected graph in which there is exactly one path between any two vertices. Each tree they are watching has the following property: the color on each edge is one of $k$ colors. If a path on the tree is colorful, it means that the path contains edges of at least two different colors.

By morning, all the magic of the trees had disappeared. Vito and Karlo still remember the endpoints of $m$ colorful paths. They want to know: how many different trees (edge colorings) can satisfy the conditions? Since the answer may be very large, output it modulo $10^9+7$.

Input Format

The first line contains three integers $n, m, k$, denoting the number of nodes in the tree, the number of colorful paths remembered by Vito and Karlo, and the total number of available 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 vertex $a_i$ and vertex $b_i$.

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

Output Format

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

3 1 2
1 2
2 3
1 3

2

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

0

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

6

Hint

[Sample 1 Explanation]

In the first case, the edge between vertex $1$ and vertex $2$ is colored $1$, and the edge between vertex $2$ and vertex $3$ is colored $2$.

In the second case, the edge between vertex $1$ and vertex $2$ is colored $2$, and the edge between vertex $2$ and vertex $3$ is colored $1$.

[Constraints and Notes]

This problem uses bundled subtasks.

• 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 \le n \le 15, k = 2$.
• Subtask 5 (65 pts): No additional constraints.

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

[Hints and Explanation]

The score distribution follows the original COCI problem, with a full score of $110$.

Translated from T5 Šarenlist, COCI2021-2022 CONTEST #4.

Translated by ChatGPT 5