Велике завдання#11095

Велике завдання

1 секунда

128 мегабайтів

Легка

Цього разу Фуфелшмерц задумав такий великий підступ, що Перрі не впорається з ним самотужки. Тому він вирішив покликати своїх колег спецагентів з О.Б.К.А.

В офісі О.Б.К.А. є $n$ кабінетів, які з'єднані $n - 1$ n - 1 коридором. З будь-якого кабінету можна дістатися коридорами до будь-якого іншого. Іншими словами, офіс О.Б.К.А. являє собою дерево, вершини якого відповідають кабінетам, а ребра — коридорам. У кожному кабінеті сидить рівно один спецагент, у кабінеті номер $v$ сидить спецагент, що володіє навичкою $c_{v}$ c_v. Всього є $m$ різних навичок, пронумерованих від $1$ до $m$ .

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

Допоможіть Перрі обчислити кількість способів, якими він може вибрати загін на завдання. Оскільки це число може бути великим, виведіть залишок від ділення цього числа на $998244353$ .

Вхідні дані

У першому рядку дано два цілих числа $n$ і $m$ ( $1 \leq n \leq 1 0^{4}$ 1 \le n \le 10^4, $1 \leq m \leq 10$ 1 \le m \le 10) — кількість кабінетів і кількість різних навичок.

У наступному рядку дано $n$ цілих чисел $c_{i}$ c_i ( $1 \leq c_{i} \leq m$ 1 \le c_i \le m) — навички спецагентів.

У наступних $n - 1$ n - 1 рядках дано по два цілих числа $a_{i}$ a_i і $b_{i}$ b_i ( $1 \leq a_{i}, b_{i} \leq n$ 1 \le a_i, b_i \le n) — номери кабінетів, з'єднаних $i$ -м коридором.

Гарантовано, що офіс О.Б.К.А. являє собою дерево.

Вихідні дані

Виведіть одне ціле число — кількість способів вибрати загін спецагентів за модулем $998244353$ .

Приклади

Приклад 1

Приклад 2

Приклад 3