Helga Hufflepuff's Cup

Harry와 Ron and Hermione는 Helga Hufflepuff's 컵이 호크룩스라는 사실을 알아냈다. Hermione은 Bellatrix Lestrange와의 만남을 통해 그 컵이 Gringott's Wizarding Bank에 있는 Bellatrix 가문의 금고에 있다는 것을 알게 되었다.

The Wizarding 은행은 총 n개의 금고로 이루어진 트리 형태이며, 각 금고에는 1부터 m 사이의 수로 나타내는 유형이 있다. 트리는 사이클이 없는 무방향 연결 그래프이다.

보안 수준이 가장 높은 금고는 k 유형이며, k 유형의 모든 금고는 보안 수준이 가장 높다.

보안 수준이 가장 높은 금고는 최대 x개일 수 있다.

또한 어떤 금고의 보안 수준이 가장 높다면, 그 금고와 인접한 금고들은 보안 수준이 가장 높지 않으며 그 유형은 k보다 작음이 보장된다.

Harry는 Bellatrix의 금고에 도달하는 최적의 경로를 쉽게 찾을 수 있도록 모든 가능성을 고려하려 한다. 따라서 Gringotts의 트리 구조가 주어질 때, 위 조건을 만족하도록 각 금고에 유형을 부여하는 가능한 방법의 수를 구해야 한다.

입력의 첫 번째 줄에는 공백으로 구분된 두 정수 n와 m가 주어진다. 이는 금고의 수와 가능한 서로 다른 금고 유형의 수이다. (1 ≤ n ≤ 105, 1 ≤ m ≤ 109).

다음 n - 1개의 각 줄에는 공백으로 구분된 두 정수 ui와 vi (1 ≤ ui, vi ≤ n)가 주어진다. 이는 i-th 간선을 나타내며, 두 금고 ui와 vi 사이에 경로가 있음을 보여 준다. 주어진 그래프가 트리임이 보장된다.

입력의 마지막 줄에는 두 정수 k와 x (1 ≤ k ≤ m, 1 ≤ x ≤ 10)가 주어진다. 이는 보안 수준이 가장 높은 금고의 유형과 보안 수준이 가장 높은 금고의 가능한 최대 개수이다.

조건에 따라 각 금고에 유형을 부여하는 방법의 수를 109 + 7로 나눈 나머지를 하나의 정수로 출력한다.

테스트 케이스 1에서는 보안 수준이 가장 높은 금고를 둘 수 없다. 그 유형이 1이므로 인접한 금고의 유형은 1보다 작아야 하는데, 이는 허용되지 않기 때문이다. 따라서 가능한 조합은 모든 금고의 유형이 2인 단 하나뿐이다.