Byteman 发明了一种名为 ByteCrypt 的新型半数字签名系统。在该系统中，每位用户都会收到一个边长为 $n$ 的空心立方体作为个人密钥，用于签署文档。立方体的每个面都被划分为 $n \times n$ 个区域，每个区域要么包含一个芯片（编码芯片或通用芯片），要么保持为空。所有编码芯片都是相同的；同样，所有通用芯片也是相同的。每个立方体每个面上的编码芯片图案都是相同的（每个面都可以旋转，使得所有立方体所有面上的图案完全一致）；任意两个面或任意两个立方体之间的唯一区别在于剩余区域中哪些位置放置了通用芯片。此外，所有芯片始终仅位于立方体每个面的内表面。

Bytehacker 打算破解 ByteCrypt 系统；他已经学会了如何伪造立方体密钥。他想知道他需要多少个密钥才能冒充系统中的任何用户。更准确地说，对于每一个可能的用户密钥（由每个面上通用芯片的图案以及立方体如何由各个面组成来定义），Bytehacker 希望拥有这样一个密钥：通过拆解（分离各个面）、重新放置和旋转这些面，然后重新组装成一个新的立方体，所得到的密钥与目标用户密钥相同。如果两个密钥可以通过旋转其中一个得到另一个，则称这两个密钥相同。为了不让 Bytehacker 感到沮丧，请输出所需密钥数量除以 $10^{9} + 7$ 的余数。

编写一个程序：

• 从标准输入读取每个立方体密钥的边长以及每个面上编码芯片的图案描述，
• 计算满足 Bytehacker 要求的最小密钥集合大小，
• 将结果除以 $10^{9} + 7$ 的余数写入标准输出。

输入格式

输入的第一行包含一个正整数 $n$ ($n \le 1000$)。接下来的 $n$ 行中，每行包含 $n$ 个整数 $a_{ij}$ ($a_{ij} \in \{0, 1\}$)，以空格分隔。$a_{ij} = 1$ 表示在每个面的第 $i$ 行第 $j$ 列有一个编码芯片。$a_{ij} = 0$ 表示相应的区域没有编码芯片，因此它可以为空，或者包含一个通用芯片。

输出格式

输出仅一行，包含一个整数，即 Bytehacker 所需的密钥数量对 $10^{9} + 7$ 取模的结果。

样例

输入 1

3
1 0 0
1 1 1
0 0 1

输出 1

5005