题目描述

译自 COCI 2021/2022 Contest #4 T5「Šarenlist」

在一个温暖的夏夜，Vito 和他的朋友 Karlo 躺在一片森林空地里看星星。突然，Vito 大喊「Karlo 快看！我们周围的树在变换颜色！」「我超好炫酷」Karlo 震惊地说。确实，森林中的树枝开始变换颜色了。

在被多彩的树木震惊的同时，Vito 和 Karlo 注意到关于这些树木的一些事实。他们看到的每棵树都可以用图论中的树来表示，即，无向图中每对节点之间只有唯一一条路径。他们看到的树都有如下性质：树上的每条边都用 $k$ 种不同的颜色之一染色。树上的一些路径是多彩的，意味着这样的路径上的边至少有两种不同的颜色。

清晨到来了，现在树魔法消失了。为了重温这段经历，Vito 和 Karlo 要求你解决如下的问题。给定一棵树和树上 $m$ 对点，确定树边的染色方案数，使得由这 $m$ 对点确定的 $m$ 条路径都是多彩的。因为这个数可能很大，输出它对 $10^9+7$ 取模后的值。

输入格式

第一行包含三个正整数 $n,m,k$，分别表示树的节点数，要求是多彩的路径数量和树边的可能颜色数。

接下来 $n-1$ 行，第 $i$ 行两个整数 $a_i,b_i$，表示一条树边。

接下来 $m$ 行，第 $j$ 行包含一对整数 $c_j,d_j$，表示要求是多彩的路径的两个端点。节点 $c_j$ 和 $d_j$ 不是相邻的。

输出格式

输出一行一个整数，表示使得由这 $m$ 对点确定的 $m$ 条路径都是多彩的树边染色方案数对 $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

数据范围与提示

对于全部数据，$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$。

详细子任务附加限制及分值如下表所示：