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.

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 the day number the administrator-robot will rust in.