ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU contest. Petrozavodsk training camp. Winter 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Work for Robots

Time limit: 2.0 second
Memory limit: 64 MB
There are n robots on planet PTZZZ. Some of the robots are friends, and some of them are not.
Once a day some of the robots go to work and all the other robots go to a theme park and have fun. At least one robot should go to work. An administrator-robot decides who should go to work and who should have fun. The work is so important for robots that the first day when the administrator-robot made his decision was named the First day of the World.
If it turns out that the group of robots that goes to work is the same as the group in any day before, the administrator-robot will rust of sadness. Moreover, the law doesn't allow the administrator-robot to form a working group in such a way that there will be a pair of robots in this group that are not friends.
The administrator-robot doesn't want to rust, so since the first day he tries to form a different working group. However, the administrator-robot will rust sooner or later. Your task is to calculate the day number when this will happen.

Input

The first line contains an integer n, the number of robots on PTZZZ (1 ≤ n ≤ 50). Each of the next n lines contains n digits. j-th digit in i-th line is 1 if i-th and j-th robots are friends, and 0 otherwise. It is guaranteed that i-th digit in i-th line is equal to zero, and j-th digit in i-th line is equal to i-th digit in j-th line.

Output

Output the day number the administrator-robot will rust in.

Sample

inputoutput
6
011100
101100
110100
111000
000001
000010
19
Problem Author: Mikhail Kolodyazhniy (prepared by Alex Samsonov)
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009
To submit the solution for this problem go to the Problem set: 1695. Work for Robots