In ultimul timp, Balaurul
Arhirel se joaca cu cei 100
de balauri de la el din cartier un joc inventat de Arhirel. Jocul NA are N
piese si se joaca astfel: la inceputul jocului, fiecare piesa se numeroteaza (de
la 1 la N)
si se trag la sorti legaturile dintre piese. Legaturile sunt intr-o singura directie.
Se poate totusi sa exista 2
legaturi intre 2 piese,
dar de directii opuse.
Scopul jocului este formarea de cat mai multe configuratii cu aceste N piese. Fiecare jucator incearca pe rand sa formeze o configuratie care nu a mai fost pana in acel moment.
O configuratie se formeaza in urmatorul fel. Se incepe cu piesa 1
tot timpul. De la aceasta se alege o piesa care e legata direct de piesa 1,
adica exista o legatura de la piesa 1
la ea. Se retine aceasta legatura (ea formeaza configuratia). Urmatorii pasi constau
in alegerea de piese noi (care nu au fost inca alese) care sunt legate direct
de una dintre piesele alese, adica exista o legatura de la una dintre piesele
alese la ea. Se retin toate legaturile folosite. Procedeul se repeta pana cand
toate cele N piese au fost
luate.
Configuratia este practic data de cele N-1 legaturi folosite.
Toti balaurii din cartieri sunt tari la informatica, asa ca nimeni nu o sa aiba probleme sa gaseasca o configuratie noua. Problema e ca la un moment dat chiar nu mai sunt alte configuratii, iar cel care castiga este cel care formeaza ultima configuratie posibila.
B.A. vrea tot timpul sa castige, asa ca va cere ajutorul ca sa stie unde sa se aseze si vrea sa stie restul impartirii numarului de configuratii la 101.
Cerinta
Ajutati-l pe Balaurul Arhirel sa castige, adica aflati numarul de configuratii modulo 101.
Date de intrare
Pe prima linie a fisierului na.in se afla un numar natural N reprezentand numarul de piese. Pe urmatoarele N
linii se afla cate N cifre binare, reprezentand legaturile. Practic, a j-a
cifra de pe linia i reprezinta daca exista legatura de la piesa i
la piesa j. 0
inseamna ca nu exista legatura, iar 1
inseamna ca exista.
Date de iesire
Fisierul na.out va contine o linie cu un singur numar, si anume numarul de configuratii modulo 101.