CSES - Kaverit
  • 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