2861 -- Cycle with 6 vertices

Language:

Cycle with 6 vertices

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 474		Accepted: 179
Case Time Limit: 1000MS

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

Sample Output

Hint

If there are 6 cities and all bits of the matrix is 1, which means all cities are connected with all of others, the answer is 60. For 7 cities, the answer is 420.

Source

Hooyeon Lee (ltdtl@POJ)