当前没有测试数据。

题目描述

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$ 不相邻。

输出格式

一行一个答案。

数据范围

对于 $100\%$ 的数据，$3\le a_i,b_i,c_j,d_j\le n\le 60$，$1\le m\le 15$，$2\le k\le 10^9$。