== include(page="template/taskheader" task_id="caterinca") ==

Poveste şi cerinţă...

_Nota de traducere: enuntul este tradus din Engleza_
 
bq. Aceasta problema este despre "caterinca", un cuvant romanesc care se traduce, aproximativ, in "smecherie" -- desi o traducere exacta nu este usor de gasit
 
Tanaka vine in vizita la amicul sau, George Mirihcihc. Casa lui poate fi modelata ca un arbore cu $N$ noduri, unde nodurile sunt camere, si muchiile sunt coridoare. In fiecare camera, se tine cate o petrecere, fiecare petrecere avand cate un $indice de caterinca$. Cea de a $i$-a petrecere are indicele de caterinca egal cu $c{~i~}$. Tanaka iubeste numarul prim $M$. Astfel, cand el ajunge, DJ PyroSava va inmulti indicii de caterinca a tuturor petrecerilor cu un numar aleator prim $X$, care satisface $X < M$. Acum, Tanaka este obosit din cauza calatoriei, deci nu poate vizita petrecerile din toate camerele. Astfel, el va alege, in mod aleator, sa viziteze o multime conexa de noduri de marime *exact* $K$. Caterinca totala pe care o va trai Tanaka este egala cu produsul indicilor de caterinca (dupa inmultirea lui DJ PyroSava) a tuturor camerelor vizitate. Consideram acum valoarea anticipata a acestei caterinci totale. Sa presupunem ca este $p / q$. Care este valoarea lui $pq^-1^ mod M$ (unde $q^-1^$ reprezinta inversul modular al lui $q$ fata de $M$) ?

h2. Date de intrare

Fişierul de intrare $caterinca.in$ ...

Fişierul de intrare $caterinca.in$ va incepe cu un numar $T$, numarul de teste din fisier.
Fiecare test incepe o linie care contine numerele $N, M, K$.
A doua linie a unui test va contine $N$ numere intregi, valorile lui $c{~i~}$, in ordine.
Urmatoarele $N-1$ linii vor contine fiecare cate o pereche $i, j$, care reprezinta o muchie intre nodul $i$ si nodul $j$.

h2. Date de ieşire

În fişierul de ieşire $caterinca.out$ ...

În fişierul de ieşire $caterinca.out$ se vor afisa cate $T$ randuri, fiecare continand raspunsul pentru cate un test.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $T ≤ 3$
* $1 ≤ N ≤ 1.000.000$
* $0 ≤ c{~i~} ≤ 1.000.000.000$
* $1 ≤ M ≤ 20.000$
* $1 ≤ K ≤ N$
* $1 ≤ NK ≤ 10.000.000$

h2. Exemplu
table(example). |_. caterinca.in |_. caterinca.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
3 23 3
2 3 2
3 1
3 2
4 23 4
2 2 4 3
1 4
2 4
3 2
4 23 4
3 3 3 3
2 4
1 3
2 1
| 3
15
21

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="caterinca") ==