Мечта Юлии наконец-то сбылась: она стала руководителем Отдела Общего Управления Иннополиса (ООУИ)! В её отделе всё устроено наиболее современным образом: документы разрабатываются на компьютерах с использованием программного обеспечения последнего поколения.
В Отделе имеется $$$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$$$.
| |} Подзадача | Баллы | Ограничения |
| 1 | 5 | $$$n, k \le 8$$$ |
| 2 | 5 | $$$k = 2$$$ |
| 3 | 5 | все $$$a_i$$$ равны $$$0$$$ |
| 4 | 10 | $$$n, k \le 300$$$ |
| 5 | 15 | $$$n, k \le 3000$$$ |
| 6 | 20 | $$$n \le 3000$$$ |
| 7 | 10 | Каждый компьютер соединён кабелем с не более, чем двумя другими компьютерами |
| 8 | 20 | $$$n \le 10^5$$$ |
| 9 | 10 | Без дополнительных ограничений |
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$$$. Следовательно, никакой план заведомо не может удовлетворять всем ограничениям.
| Название |
|---|


