В этот раз Фуфелшмерц задумал такую большую пакость, что Перри не справится с ним в одиночку. Поэтому, он решил позвать своих коллег спецагентов из О.Б.К.А.
В офисе О.Б.К.А. есть n кабинетов, которые соединены n - 1 коридором. Из любого кабинета можно добраться по коридорам до любого другого. Иными словами, офис О.Б.К.А. представляет из себя дерево, вершины которого соответствуют кабинетам, а ребра коридорам. В каждом кабинете сидит ровно один спецагент, в кабинете номер v сидит спецагент, обладающий навыком c[v]
. Всего есть m различных навыков, пронумерованных от 1 до m.
Перри хочет выбрать такой отряд спецагентов, что для каждого из m навыков в этом отряде будет хотя бы один спецагент с таким навыком. А также, если Перри возьмет в отряд спецагентов из кабинетов v и u, он также обязательно возьмет в отряд всех спецагентов, которые сидят в кабинетах, расположенных на простом пути между u и v.
Помогите Перри вычислить количество способов, которыми он может выбрать отряд на задание. Так как это число может быть большим, выведите остаток от деления этого числа на 998 244 353.
В первой строке даны два целых числа n и m (1 ≤ n ≤ 10^4
, 1 ≤ m ≤ 10) - количество кабинетов и количество различных навыков.
В следующей строке даны n целых чисел c[i]
(1 ≤ c[i]
≤ m) - навыки спецагентов.
В следующих n - 1 строках даны по два целых числа a[i]
и b[i]
(1 ≤ a[i]
, b[i]
≤ n) - номера кабинетов, соединенных i-м коридором.
Гарантируется, что офис О.Б.К.А. представляет из себя дерево.
Выведите одно целое число количество способов выбрать отряд спецагентов по модулю 998 244 353.