FMI NO STRESS 12 | Eritrocit

Se dă un arbore cu $N$ noduri, numerotate de la $1$ la $N$, în care fiecare nod are asociată o culoare. Fiecare culoare este reprezentată de un număr din mulțimea $\{1, 2, \dots, N\}$. Numim componentă o mulțime de noduri care formează o regiune conexă (subgraf conex nevid al arborelui) în arbore și pentru care oricare două noduri din mulțime au aceeași culoare. Această mulțime nu trebuie să fie neapărat maximală.

Cerință

Se cere numărul de moduri distincte de a împărți toate nodurile arborelui în cel mult $K$ componente disjuncte. De vreme ce acest număr poate să fie foarte mare, se cere restul său la împărțirea cu $10^9+9$.

Două moduri, $M_{1}$ și $M_{2}$ se consideră distincte dacă există două noduri $u$ și $v$ ($1 \leq u, v \leq N$) care fac parte din aceeași componentă în $M_{1}$ și nu fac parte din aceeași componentă în $M_{2}$.

Date de intrare

Prima linie va conține numerele $N$ și $K$. A doua linie va conține $N$ numere naturale nenule mai mici sau egale decât $N$. Al $i$-lea număr reprezintă culoarea celui de-al $i$-lea nod.
Următoarele $N-1$ linii conțin fiecare câte o pereche de noduri $(u, v)$, semnificând că în arbore există muchie între nodurile $u$ și $v$.

Date de ieșire

Se va afișa un singur număr, reprezentând numărul de moduri în care se poate împărți arborele în cel mult $K$ componente, modulo $10^9 + 9$.

Restricții și precizări

• $1 \leq K \leq N \leq 200 \ 000$;
• $1 \leq u, v \leq N$;
• Pentru $9$ puncte, $1 \leq N \leq 15$, $1 \leq K \leq 4$;
• Pentru alte $8$ puncte, $K = 2$;
• Pentru alte $9$ puncte, $K = 3$;
• Pentru alte $19$ de puncte, $1 \leq K \leq N \leq 200$;
• Pentru alte $18$ puncte, $1 \leq K \leq N \leq 2 \ 000$;
• Pentru restul de $37$ puncte, nu există restricții suplimentare.

Exemplu

stdin

5 3
1 1 1 1 2
2 4
1 2
5 4
3 4

stdout

4

Explicație

Putem împărți arborele în cel mult $3$ componente în $4$ moduri. Cele patru moduri sunt:

• $\{5\}$ și $\{1, 2, 4, 3\}$;
• $\{5\}$, $\{1\}$ și $\{2, 4, 3\}$;
• $\{5\}$, $\{1, 2\}$ și $\{4, 3\}$;
• $\{5\}$, $\{1, 2, 4\}$ și $\{3\}$.