Description
A general of World Nation wants to make 6 towers at 6 distinct cities of the nation. World Nation has N cities and some of cities are connected, but others not. The general wants to know how many ways he can select 6 cities and finally build 6 towers. However, one thing is necessary: if he chooses 6 cities A, B, C, D, E, and F, they have to be connected with their neighbors. If we draw 6 cities as 6 points on a circle, we can easily realize each of 6 cities has two neighbors, one for clockwise and another for counterclockwise. For example, A has two neighbors, B and F. So the general needs to consider about the order of 6 cities because to choose (A-B-C-D-E-F-A) is not the same as to choose (A-B-D-C-E-F-A). Nevertheless, the choice (A-B-C-D-E-F-A) is the same as (A-F-E-D-C-B-A) and/or as (B-C-D-E-F-A-B) because they can be made by reversion or rotation.
Now, it is time to help the general.
Input
The first line has a positive integer N (6 ≤ N ≤ 111), which indicates the number of cities. Information on connection of the cities is given by an adjacent-matrix: if city A and city B is connected, bits of A-row B-column and B-row A-column are 1. Otherwise, both are 0. There is no space in a line.
Output
If the number of ways is K, just output K mod 9901 because K can be very large.
Sample Input
6
010001
101000
010100
001010
000101
100010
Sample Output
1
http://poj.org/problem?id=2861
