Большое задание
В этот раз Фуфелшмерц задумал такую большую пакость, что Перри не справится с ним в одиночку. Поэтому, он решил позвать своих коллег спецагентов из О.Б.К.А.
В офисе О.Б.К.А. есть n кабинетов, которые соединены n - 1 коридором. Из любого кабинета можно добраться по коридорам до любого другого. Иными словами, офис О.Б.К.А. представляет из себя дерево, вершины которого соответствуют кабинетам, а ребра коридорам. В каждом кабинете сидит ровно один спецагент, в кабинете номер v сидит спецагент, обладающий навыком c[v]
. Всего есть m различных навыков, пронумерованных от 1 до m.
Перри хочет выбрать такой отряд спецагентов, что для каждого из m навыков в этом отряде будет хотя бы один спецагент с таким навыком. А также, если Перри возьмет в отряд спецагентов из кабинетов v и u, он также обязательно возьмет в отряд всех спецагентов, которые сидят в кабинетах, расположенных на простом пути между u и v.
Помогите Перри вычислить количество способов, которыми он может выбрать отряд на задание. Так как это число может быть большим, выведите остаток от деления этого числа на 998 244 353.
Giriş verilənləri
В первой строке даны два целых числа 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-м коридором.
Гарантируется, что офис О.Б.К.А. представляет из себя дерево.
Çıxış verilənləri
Выведите одно целое число количество способов выбрать отряд спецагентов по модулю 998 244 353.