Fişierul intrare/ieşire:salaj.in, salaj.outSursăONIS 2015 Runda Finala
AutorEugenie Daniel Posdarascu, Mihai CalanceaAdăugată deONIS2015ONIS2015 ONIS2015
Timp execuţie pe test1.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Salaj

Orasul Salaj este foarte mic (FOARTE FOARTE FOARTE MIC). Orasul are N blocuri (in teorie are 2,3 blocuri dar vom presupune fictiv ca N ≤ 50) si momentan 0 carari construite intre blocuri (in final or sa fie M astfel de carari). O componenta Salajeneasca este o componenta de blocuri in care din orice bloc poti sa ajungi in orice alt bloc (in termeni de grafuri mai este numita si componenta tare conexa). Plictisit ca nu are ce sa faca in orasul lui (deoarece este prea mic), Razvan s-a decis sa joace un joc. De fiecare data cand este construita o carare noua, Razvan isi noteaza pe o foaie cate componente Salajenesti exista in oras. La final dupa ce au fost construite toate cele M carari, Razvan obtine un sir de lungime M. Dupa atata munca, personajul nostru se decide sa se duca in club dar repede realizeaza ca se afla in Salaj si nu are asa ceva. Suparat, se intreaba cate siruri distincte poate obtine in functie de modul in care sunt construite cele M carari. Observatie: sunt mai multe moduri de a obtine acelasi sir dar pe Razvan il intereseaza doar numarul de siruri distincte. Ca urmare, un sir o sa fie numarat o singura data.

Date de intrare

Fişierul de intrare salaj.in va contine pe prima linie un numar natural T, reprezentand numarul de teste. Pe urmatoarele T linii vor fi cate 3 numere naturale N, M si MOD.

Date de ieşire

Fişierul de ieşire salaj.out va contine T linii, pe linia i fiind raspunsul pentru testul i. O linie va contine M valori. A i-a valoare reprezentand numarul de siruri pe care le poate obtine Razvan modulo MOD daca are N blocuri si i muchii (unde N, M si MOD sunt valorile corespunzatoare testului respectiv).

Restricţii

  • 1 ≤ N ≤ 50
  • 1 ≤ T ≤ 10
  • 1 ≤ M ≤ N * (N - 1)
  • O carare este o muchie orientata
  • 1 ≤ MOD ≤ 1.000.000.000
  • Legenda spune ca Salaj ar fi de fapt judet dar nimeni nu stie unde se afla.

Exemplu

salaj.insalaj.out
2
5 10 666013
6 9 10
1 2 4 9 21 50 110 209 351 546
1 2 4 9 1 1 6 0 7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?