Fişierul intrare/ieşire:	radacina2.in, radacina2.out	Sursă	Algoritmiada 2013, Runda 4
Autor	Eugenie Daniel Posdarascu	Adăugată de	Ionescu Vlad •vladii
Timp execuţie pe test	0.175 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Radacina2

Se dau N arbori, initial fiecare arbore contine exact un nod (si nicio muchie): arborele i este format din nodul i. Definim o operatie UNITE (i, j) asupra nodurilor date in felul urmator:

• operatia este valida doar daca nodurile i si j sunt radacinile arborilor din care fac parte;
• daca arborele cu radacina in nodul i are mai putine noduri decat arborele cu radacina in j, atunci j devine tatal nodului i (se unesc cei doi arbori printr-o muchie orientata de la nodul j la nodul i);
• daca arborele cu radacina in nodul i are mai multe noduri decat arborele cu radacina in j, atunci i devine tatal nodului j (se unesc cei doi arbori printr-o muchie orientata de la nodul i la nodul j);
• daca arborele cu radacina in nodul i are acelasi numar de noduri ca arborele cu radacina in nodul j, atunci nodul cu indicele mai mare devine tatal nodului cu indicele mai mic (se unesc cei doi arbori printr-o muchie orientata, la fel ca mai sus).

Dupa ce se efectueaza N-1 operatii de tip UNITE, in final ramane un singur arbore. Determinati in cate moduri (modulo un numar natural P dat) se pot efectua operatiile UNITE astfel incat arborele ramas sa aiba radacina in nodul X, unde X este un numar dat.

Date de intrare

Fişierul de intrare radacina2.in contine pe prima linie trei numere naturale: N X P, despartite prin cate un spatiu, cu semnificatia din enunt.

Date de ieşire

În fişierul de ieşire radacina2.out se afla pe prima linie un singur numar natural, reprezentand numarul de moduri, modulo P, in care se pot efectua operatiile de tip UNITE asupra celor N arbori initiali (formati doar dintr-un nod), astfel incat, dupa N-1 operatii, sa ramana un singur arbore cu radacina in nodul X.

Restricţii

• 1 ≤ N ≤ 70
• 1 ≤ X ≤ N
• 1 ≤ P ≤ 1.000.000.000
• Doua operatii UNITE (x₁, y₁) si UNITE (x₂, y₂) se considera diferite daca { x₁, y₁} != {x₂, y₂} (cele doua multimi sunt diferite, cu alte cuvinte exista un nod intr-o operatie care nu se afla in cealalta).
• Operatia UNITE (x, y) se considera identica cu operatia UNITE (y, x).
• Doua moduri de efectuare a operatiilor se considera diferite daca exista un indice i ( 1 ≤ i ≤ N-1 ), astfel incat operatiile UNITE efectuate la pasul i in cele doua moduri sunt diferite.

Exemplu

Explicaţie

Cele doua moduri de efectuare a operatiilor sunt:
1. UNITE (1, 2), UNITE (2, 3), UNITE (2, 4)
2. UNITE (1, 2), UNITE (2, 4), UNITE (2, 3)

Cum se trimit solutii?