teroristi

Gruparea de terorişti DFG ameninţă liniştea Iaşiului. Serviciile Secrete Iaşi (SSI) au aflat că gruparea este formată din N terorişti, numerotaţi de la 1 la N.

Luptătoarea V Power vrea să anihileze fiecare terorist pentru a restabili siguranţa oraşului. V Power ştie că există K restricţii date prin perechi de forma (x, y), cu semnificaţia că teroristul y poate fi eliminat doar după ce a fost eliminat teroristul x (altfel nu poate fi localizat nici măcar de SSI).

Înainte de a porni la drum, V Power vrea să ştie în câte moduri poate anihila toţi teroriştii folosind desigur tehnici avansate de taekwondo. Cu alte cuvine se cere să se determine numărul de modalităţi modulo R de anihilare a tuturor teroriştilor, conform celor K restricţii. O modalitate de anihilare a tuturor teroriştilor înseamnă alegerea ordinii de eliminare a lor.

Date de intrare

Pe prima linie a fişierului teroristi.in se găsesc trei numere naturale: N, K, R separate prin câte un spaţiu, având semnificaţia din enunţ.
Pe fiecare dintre următoarele K linii se găsesc câte două numere naturale x y, separate printr-un spaţiu având semnificaţiile din enunţ.

Date de ieşire

Pe prima linie a fişierului teroristi.out se va afişa un număr natural Z reprezentând numărul de modalităţi modulo R în care se poate anihila gruparea.

Restricţii

• N ≤ 100
• K ≤ 100
• 1 ≤ x, y ≤ N
• În cele K restricţii vor fi menţionaţi cel mult 20 terorişti
• R este prim, $R < 10^9$
• Se garantează că există cel puţin o modalitate de eliminare a teroriştilor

Exemplu:

teroristi.in

4 3 666013
1 2
4 3
1 3

teroristi.out

5

Explicaţii

Cele 5 modalităţi sunt:

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