温暖的夏夜。Vito 和他的朋友 Karlo 躺在森林空地上看星星。突然，Vito 惊呼道：“Karlo，快看！我们周围的树正在变色！”“哇，真多彩啊，”Karlo 惊叹道。确实，森林里的树枝开始变换颜色。

被这些多彩的树木所吸引，Vito 和 Karlo 注意到了一些关于它们的特性。他们看到的每一棵树都可以表示为一棵树图，即一种在每对节点之间存在唯一路径的无向图。他们观察的树具有这样的属性：树的每条边都被涂上了 $k$ 种不同颜色中的一种。树上的一些路径是“多彩的”，意味着这样的路径包含至少两种不同颜色的边。

早晨已经到来，树木的魔法消失了。为了重温这种体验，Vito 和 Karlo 请你解决以下问题。给定一棵树和树上的 $m$ 对节点，确定树边的不同染色方案数，使得这 $m$ 对节点所确定的 $m$ 条路径中的每一条都是多彩的。由于这个数字可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含三个正整数 $n$、$m$ 和 $k$ ($3 \le n \le 60, 1 \le m \le 15, 2 \le k \le 10^9$)，分别表示树的节点数、需要多彩的路径数量以及树枝可能的颜色数量。

接下来的 $n - 1$ 行，第 $i$ 行包含一对正整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n$)，表示树的一条边。

接下来的 $m$ 行，第 $j$ 行包含一对正整数 $c_j$ 和 $d_j$ ($1 \le c_j, d_j \le n$)，表示需要多彩的路径的两个端点。节点 $c_j$ 和 $d_j$ 不相邻。

输出格式

仅输出一行，表示使得 $m$ 条给定路径均为多彩的树边染色方案数，对 $10^9 + 7$ 取模。

子任务

样例

输入格式 1

3 1 2
1 2
2 3
1 3

输出格式 1

2

说明

这棵树仅由两条边组成，它们都是节点 1 和 3 之间多彩路径的一部分。因此，这两条边必须具有不同的颜色。一种染色方案是将边 1-2 涂成颜色 1，将边 2-3 涂成颜色 2；另一种方案是通过交换颜色，使得 1-2 涂成颜色 2，而 2-3 涂成颜色 1。

输入格式 2

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

输出格式 2

0

输入格式 3

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

输出格式 3

6