C. Чаша Пенелоппы Пуффендуй
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Гарри, Рон и Гермиона обнаружили, что чаша Пенелоппы Пуффендуй является крестражем. В результате встречи с Белатриссой Лестрейндж Гермиона узнала, что чаша находится в семейном хранилище Лейстренджей в банке Гринготтс.

Волшебный банк представляет собой дерево из n хранилищ, каждое из которых имеет тип, определяемый целым числом от 1 до m. Деревом называется неориентированный связный граф без циклов.

Хранилища с идеальной охраной имеют тип k, все хранилища с типом k имеют идеальную охрану.

В банке может быть не более x хранилищ с идеальной охраной.

Кроме того, если хранилище имеет идеальную охрану, все соседние хранилища не имеют идеальной охраны, а их тип строго меньше k.

Гарри хочет рассмотреть все возможные варианты устройства банка. Он знает расположение хранилищ, поэтому его интересует количество возможных вариантов назначить хранилищам типы, чтобы все условия выполнялись.

Входные данные

В первой строке содержатся два целых числа n и m — количество хранилищ и количество различных типов хранилищ, соответственно (1 ≤ n ≤ 105, 1 ≤ m ≤ 109).

В следующей n - 1 строке содержатся пары целых чисел ui и vi (1 ≤ ui, vi ≤ n), описывающее i-е ребро, которое соединяет хранилища ui и vi. Гарантируется, что заданный граф является деревом.

В последней строке содержатся два целых числа k и x (1 ≤ k ≤ m, 1 ≤ x ≤ 10) — тип хранилищ с идеальной охраной и максимальное количество таких хранилищ.

Выходные данные

Выведите единственное число — количество способов назначить хранилищам типы для выполнения всех условий по модулю 109 + 7.

Примеры
Входные данные
4 2
1 2
2 3
1 4
1 2
Выходные данные
1
Входные данные
3 3
1 2
1 3
2 1
Выходные данные
13
Входные данные
3 1
1 2
1 3
1 1
Выходные данные
0
Примечание

В примере 1, не может быть хранилищ с идеальной охраной, так тип хранилища с идеальной охраной равен 1, что значит, что соседние хранилища должны иметь тип меньше чем 1, что невозможно. Поэтому единственно возможный вариант — когда все хранилища имеют тип 2.