当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
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.
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.
If the number of ways is K, just output K mod 9901 because K can be very large.
6 010001 101000 010100 001010 000101 100010
1
| Case time limit(单组数据时间限制) | 1000MS |
| 时间上限 | 内存上限 |
| 7000 | 65536 |