E. Draft Laws
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мечта Юлии наконец-то сбылась: она стала руководителем Отдела Общего Управления Иннополиса (ООУИ)! В её отделе всё устроено наиболее современным образом: документы разрабатываются на компьютерах с использованием программного обеспечения последнего поколения.

В Отделе имеется $$$n$$$ рабочих компьютеров, к каждому из которых прикреплён уникальный номер от $$$1$$$ до $$$n$$$ и опытный сотрудник, работающий только на нём. Некоторые пары компьютеров соединены кабелем, позволяющим передавать данные между этими компьютерами в обе стороны. При этом, между любыми двумя компьютерами существует ровно один способ передать данные по кабелям, не используя никакой кабель дважды. Иными словами, сеть компьютеров и кабелей образует дерево.

В настоящий момент в отделе разрабатывается $$$k$$$ законопроектов. Юлии нужно составить план на завтра: она должна для каждого компьютера определить, какой из $$$k$$$ законопроектов будет править сотрудник за этим компьютером. Каждый сотрудник должен работать ровно над одним законопроектом в течение дня, но, при этом, один законопроект может одновременно редактироваться на нескольких компьютерах (или даже ни на одном). Некоторые сотрудники имеют свой любимый законопроект, и они согласны редактировать только его. Кроме того, в соответствии с законодательством, нельзя допустить, чтобы на двух компьютерах, соединённых кабелем, редактировался один и тот же законопроект.

Юля очень взволнована перед своим первым рабочим днем, и ей интересно, сколько у неё есть способов составить план на завтра, удовлетворив все пожелания сотрудников и требования законодательства. Помогите ей найти это число способов! Так как искомое число может быть большим, найдите его по модулю $$$10^9+7$$$.

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

Первая строка содержит два числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$2 \le k \le 10^9$$$) — число компьютеров в Отделе Общего Управления Иннополиса и число разрабатываемых законопроектов соответственно.

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le k$$$), где $$$a_i$$$ — номер любимого законопроекта сотрудника за компьютером $$$i$$$, или $$$0$$$, если он согласен редактировать любой законопроект.

В каждой из следующих $$$n - 1$$$ строк дано по два целых числа $$$u_j$$$ и $$$v_j$$$ — номера компьютеров, соединенных кабелем ($$$1 \le u_j, v_j \le n$$$; $$$u_j \neq v_j$$$). Гарантируется, что сеть компьютеров и кабелей образует дерево.

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

В единственной строке выведите одно целое число — количество способов составить план на завтра, удовлетворяющий всем требованиям, взятое по модулю $$$10^9+7$$$.

Система оценки
|}

Подзадача

БаллыОграничения
15$$$n, k \le 8$$$
25$$$k = 2$$$
35все $$$a_i$$$ равны $$$0$$$
410$$$n, k \le 300$$$
515$$$n, k \le 3000$$$
620$$$n \le 3000$$$
710Каждый компьютер соединён кабелем с не более, чем двумя другими компьютерами
820$$$n \le 10^5$$$
910Без дополнительных ограничений
Примеры
Входные данные
4 3
0 0 1 2
1 2
2 3
2 4
Выходные данные
2
Входные данные
4 3
1 0 0 0
1 2
2 3
2 4
Выходные данные
8
Входные данные
4 1000000000
0 2 2 0
1 2
2 3
3 4
Выходные данные
0
Примечание

В первом примере на компьютерах $$$3$$$ и $$$4$$$ уже определены законопроекты $$$1$$$ и $$$2$$$, поэтому для компьютера $$$2$$$ есть только один возможный законопроект: $$$3$$$. А для компьютера $$$1$$$ можно выбрать два законопроекта ($$$1$$$ и $$$2$$$), поэтому общее число способов равно $$$2$$$.

В третьем примере на двух соседних компьютерах $$$2$$$ и $$$3$$$ уже определен один и тот же законопроект $$$2$$$. Следовательно, никакой план заведомо не может удовлетворять всем ограничениям.