第 3 题 Šarenlist (arenlist)

时间限制 1.0 s · 空间限制 256 MB · 37 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 arenlist.in，输出文件 arenlist.out。

温暖的夏夜，Vito 和他的好朋友 Karlo 躺在森林的空地上看星星。突然，Vito 大喊：“Karlo，你看！我们周围的树都在变色！”“哇，真是五彩缤纷！”Karlo 惊讶地说。的确，森林中的树枝开始变色。

题目描述

Vito 和 Karlo 被这些彩色的树迷住了，他们同时也注意到了一些事物。他们正在看的每棵树都可以看做是一个树图，即任意两点之间仅存在一条路径的无向图。他们正在看的每棵树都有这样的特点：每条边上的颜色都是 $k$ 种颜色中的一种。如果树上的一个路径是彩色的，意味着这条路径上至少包含两种不同颜色的边。

早上树的魔力全部消失了。Vito 和 Karlo 还记得 $m$ 条彩色路径的起点和终点。他们想知道：满足条件的树的树有多少种可能？由于答案可能很大，所以请将答案对 $10^9 + 7$ 取模。

输入格式

第一行包含三个整数 $n, m, k$，分别表示树上的节点数、Vito 和 Karlo 所记得的彩色路径的个数和树枝的颜色总数。

接下来 $n - 1$ 行，第 $i + 1$ 行包含两个整数 $a_i, b_i$，表示点 $a_i$ 和点 $b_i$ 之间有一条树边。

接下来 $m$ 行，第 $n + j$ 行包含两个整数 $c_j, d_j$，表示从点 $c_j$ 到点 $d_j$ 之间有一条彩色路径。保证 $c_j$ 和 $d_j$ 不相邻。

输出格式

仅一行，输出满足条件的树的可能性，答案需对 $10^9 + 7$ 取模。

样例

样例 1

输入：

3 1 2
1 2
2 3
1 3

输出：

2

样例 2

输入：

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

输出：

0

样例 3

输入：

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

输出：

6

提示

【样例 1 解释】

第一种情况是点 1 和点 2 之间的边涂颜色 1，点 2 和点 3 之间的边涂颜色 2。

第二种情况是点 1 和点 2 之间的边涂颜色 2，点 2 和点 3 之间的边涂颜色 1。

【数据规模与约定】

本题采用子任务捆绑测试。

• Subtask 1（10 pts）：$m = 1$。
• Subtask 2（15 pts）：$m = 2$。
• Subtask 3（10 pts）：每个树边最多属于 $m$ 条彩色路径中的一条。
• Subtask 4（10 pts）：$1 \le n \le 15, k = 2$。
• Subtask 5（65 pts）：没有额外限制。

对于 100% 的数据，$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$。

【提示与说明】

** **