Fişierul intrare/ieşire:	caterinca.in, caterinca.out	Sursă	AGM 2019, runda finala
Autor	Tamio-Vesa Nakajima	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	3.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Caterinca

Nota de traducere: enuntul era original in engleza

Aceasta problema este despre "caterinca", un cuvant Romanesc care se traduce, aproximativ, in "caterinca" sau "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) ?

Date de intrare

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.

Date de ieşire

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

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

Exemplu

Cum se trimit solutii?