bq. 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$) ?

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