Cubes

Byteman invented a new semi-digital signature system called ByteCrypt. In this system every user receives a personal key shaped like a hollow cube with edge length $n$, which is used to sign documents. Every face of every cube is divided into $n \times n$ regions, and each region either holds exactly one chip (an encoding chip or a general-purpose chip) or stays empty.

All encoding chips are identical, and likewise any two general-purpose chips are identical. The pattern formed by the encoding chips is the same on every face of every cube: each face can be rotated so that the encoding patterns on all faces of all cubes coincide exactly. The only thing that distinguishes two faces is which of the remaining regions hold general-purpose chips. All chips always sit on a single surface of each face, namely the surface that points toward the inside of the cube.

Bytehacker wants to break ByteCrypt; he already knows how to forge cubic keys. He would like to know how many keys he must own to be able to impersonate any user of the system. More precisely, for every possible user key (determined by the placement of general-purpose chips on each face together with how the faces are assembled into a cube) Bytehacker wants to own a key with the following property: after the key is taken apart into its six faces, and the faces are freely rearranged, rotated, and reassembled into a new cube, the result is identical to that user key. Two keys are identical when one of them can be rotated to match the other.

Write a program that:

• reads the edge length of the cubic key and the pattern of encoding chips on a face,
• computes the minimum number of keys Bytehacker needs,
• prints that number modulo $10^9 + 7$.

The first line contains one positive integer $n$ ($n \le 1000$). Each of the next $n$ lines contains $n$ integers $a_{ij} \in \{0, 1\}$ separated by single spaces. $a_{ij} = 1$ means that the region in row $i$, column $j$ of every face holds an encoding chip. $a_{ij} = 0$ means that region has no encoding chip, so it may be empty or hold a general-purpose chip.

Print a single integer: the number of keys Bytehacker needs, taken modulo $10^9 + 7$.