Šarenlist

따뜻한 여름밤. Vito와 친구 Karlo는 숲속 공터에 누워 별을 보고 있다. 갑자기 Vito가 외친다. "Karlo, 봐! 우리 주변 나무들이 색이 변하고 있어!" "우와 정말 알록달록하다"라고 Karlo가 감탄하며 말했다. 실제로 숲속 나무 가지들이 색을 바꾸기 시작했다.

알록달록한 나무에 매료된 Vito와 Karlo는 나무들에 관한 몇 가지 사실을 알아냈다. 그들이 보고 있는 나무는 각각 트리 그래프, 즉 임의의 두 노드 사이에 유일한 경로가 존재하는 무방향 그래프로 나타낼 수 있다. 그들이 보고 있는 나무는 각 간선이 서로 다른 $k$가지 색 중 하나로 칠해져 있다. 나무 위의 어떤 경로가 colorful하다는 것은 그러한 경로가 적어도 두 가지 다른 색의 간선을 포함한다는 뜻이다.

아침이 밝았고 나무 마법은 이제 사라졌다. 이 경험을 다시 되살리기 위해 Vito와 Karlo는 다음과 같은 문제를 풀어 달라고 부탁한다. 나무와 나무 위의 $m$쌍의 노드가 주어졌을 때, $m$쌍의 노드가 정하는 $m$개의 경로 각각이 colorful하도록 나무 간선을 색칠하는 서로 다른 방법의 수를 구하라. 이 수는 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력하라.

첫째 줄에 세 양의 정수 $n$, $m$, $k$ ($3 ≤ n ≤ 60$, $1 ≤ m ≤ 15$, $2 ≤ k ≤ 10^9$)가 주어진다. 각각 나무의 노드 수, colorful해야 하는 경로의 수, 나무 가지에 가능한 색의 수이다.

다음 $n - 1$개 줄의 $i$번째 줄에는 양의 정수 쌍 $a\_i$, $b\_i$ ($1 ≤ a\_i , b\_i ≤ n$)가 주어지며, 나무의 간선 하나를 나타낸다.

다음 $m$개 줄의 $j$번째 줄에는 양의 정수 쌍 $c\_j$, $d\_j$ ($1 ≤ c\_j , d\_j ≤ n$)가 주어지며, colorful해야 하는 경로의 양 끝점 레이블이다. 노드 $c\_j$와 $d\_j$는 서로 인접하지 않다.

유일한 줄에 주어진 $m$개의 경로 각각이 colorful하도록 나무 간선을 색칠하는 방법의 수를 $10^9 + 7$로 나눈 나머지를 출력하라.

첫 번째 예제에 대한 설명: 나무는 간선이 두 개뿐이고, 둘 다 노드 1과 3 사이의 colorful 경로에 속한다. 따라서 두 간선은 서로 다른 색이어야 한다. 간선 1-2를 색 1로, 2-3을 색 2로 칠하는 방법과 이 색을 서로 바꿔 1-2를 색 2로, 2-3을 색 1로 칠하는 방법이 있다.