Большое задание
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В этот раз Фуфелшмерц задумал такую большую пакость, что Перри не справится с ним в одиночку. Поэтому, он решил позвать своих коллег спецагентов из О.Б.К.А.

В офисе О.Б.К.А. есть $$$n$$$ кабинетов, которые соединены $$$n - 1$$$ коридором. Из любого кабинета можно добраться по коридорам до любого другого. Иными словами, офис О.Б.К.А. представляет из себя дерево, вершины которого соответствуют кабинетам, а ребра — коридорам. В каждом кабинете сидит ровно один спецагент, в кабинете номер $$$v$$$ сидит спецагент, обладающий навыком $$$c_v$$$. Всего есть $$$m$$$ различных навыков, пронумерованных от $$$1$$$ до $$$m$$$.

Перри хочет выбрать такой отряд спецагентов, что для каждого из $$$m$$$ навыков в этом отряде будет хотя бы один спецагент с таким навыком. А также, если Перри возьмет в отряд спецагентов из кабинетов $$$v$$$ и $$$u$$$, он также обязательно возьмет в отряд всех спецагентов, которые сидят в кабинетах, расположенных на простом пути между $$$u$$$ и $$$v$$$.

Помогите Перри вычислить количество способов, которыми он может выбрать отряд на задание. Так как это число может быть большим, выведите остаток от деления этого числа на $$$998\,244\,353$$$.

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

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ — количество кабинетов и количество различных навыков ($$$1 \le n \le 10\,000$$$, $$$1 \le m \le 10$$$).

В следующей строке даны $$$n$$$ целых чисел $$$c_i$$$ — навыки спецагентов ($$$1 \le c_i \le m$$$).

В следующих $$$n - 1$$$ строках даны по два целых числа $$$a_i$$$ и $$$b_i$$$ — номера кабинетов, соединенных $$$i$$$-м коридором ($$$1 \le a_i, b_i \le n$$$).

Гарантируется, что офис О.Б.К.А. представляет из себя дерево.

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

Выведите одно целое число — количество способов выбрать отряд спецагентов по модулю $$$998\,244\,353$$$.

Примеры

Входные данные
3 3
1 2 3
1 2
2 3
Выходные данные
1
Входные данные
4 2
1 2 2 2
1 2
1 3
1 4
Выходные данные
7
Входные данные
6 3
1 2 3 1 2 3
1 2
2 3
2 4
4 5
4 6
Выходные данные
14