Велике завдання
Цього разу Фуфелшмерц задумав таку велику капость, що Перрі не впорається з ним самотужки. Тому він вирішив покликати своїх колег спецагентів з О.Б.К.А.
В офісі О.Б.К.А. є 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.