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