- Time limit: 2.00 s
- Memory limit: 512 MB
Saat tiedot ketkä Syrjälän asukkaista ovat toistensa kavereita. Tehtävänäsi on laskea kuinka monella tavalla voidaan valita joukko Syrjälän asukkaita niin että kaikki joukossa olevat ovat keskenään kavereita. Syötteet on generoitu niin että vastaus on korkeintaan 10^6
Syöte
Syötteen ensimmäisellä rivillä on luku n, Syrjälän asukkaiden määrä. Sen jälkeen tulee n riviä. Rivillä i on n pituinen merkkijono a_i. Jos a_{i, j} = 1 niin Syrjälän asukkaat i ja j ovat kavereita ja jos a_{i, j} = 0 niin Syrjälän asukkaat i ja j eivät ole kavereita. a_{i, j} = a_{j, i} ja a_{i, i} = 0.
Tuloste
Tulosta kuinka monella tavalla voidaan valita joukko Syrjälän asukkaita niin että kaikki joukossa olevat ovat keskenään kavereita.
Rajat
- 1 \le n \le 100
Esimerkki
Syöte:
3 011 101 110
Tuloste:
7
Syöte:
4 0111 1010 1101 1010
Tuloste:
11