题目背景

数学研究员正在分析一张由正整数构成的方阵。

他希望从矩阵中选出若干元素，使每一行和每一列都恰好保留奇数个元素。同时，为了让所有被选元素的质因数能够“两两配对”，这些元素的乘积还必须是一个完全平方数。

请计算满足全部条件的选择方案数。

题目描述

给定一个 $n\times n$ 的正整数矩阵：

$$a_{i,j}\qquad (0\le i,j<n).$$

你需要选择矩阵中的一些元素。每个元素只能选择一次或不选择。

一个选择方案合法，当且仅当同时满足：

1. 矩阵的每一行都包含奇数个被选元素；
2. 矩阵的每一列都包含奇数个被选元素；
3. 所有被选元素的乘积是一个完全平方数。

两个方案不同，当且仅当至少有一个矩阵位置在其中一个方案中被选择，而在另一个方案中没有被选择。

请计算合法方案数，并对：

$$1\,000\,000\,007$$

取模。

完全平方数

若一个正整数可以表示为某个整数的平方，则称它为完全平方数。

例如：

• $1=1^2$；
• $36=6^2$；
• $324=18^2$。

从质因数分解的角度看，一个正整数是完全平方数，当且仅当它的每一种质因子的指数都是偶数。

输入格式

第一行包含一个整数 $n$，表示矩阵的行数和列数。

接下来 $n$ 行，每行包含 $n$ 个正整数。

第 $i+1$ 行的第 $j+1$ 个整数表示 $a_{i,j}$。

输出格式

输出一个整数，表示合法选择方案数对 $1\,000\,000\,007$ 取模后的结果。

数据范围

对于所有测试数据：

• $1\le n\le 20$；
• $1\le a_{i,j}\le 10^9$。

样例 1

输入

2
1 1
1 2

输出

1

解释

唯一的合法方案是选择位置 $(0,1)$ 和 $(1,0)$。

两行和两列都各有一个被选元素，且乘积为：

$$1\cdot1=1=1^2.$$

样例 2

输入

2
620 620
620 620

输出

2

解释

两种合法方案分别为：

• 选择 $(0,0)$ 和 $(1,1)$；
• 选择 $(0,1)$ 和 $(1,0)$。

样例 3

输入

3
1 2 3
4 5 6
7 8 9

输出

1

解释

唯一的合法方案选择了数值为 $1,2,3,6,9$ 的五个元素。

它们的乘积为：

$$1\cdot2\cdot3\cdot6\cdot9 =324 =18^2.$$

样例 4

输入

5
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2

输出

0

解释

由于每一行都必须选择奇数个元素，最终被选元素总数一定是奇数。

所有元素都是 $2$，因此乘积中质因子 $2$ 的指数一定是奇数，不可能构成完全平方数。

样例 5

输入

4
2 3 4 5
6 7 8 9
10 11 12 13
14 15 16 17

输出

4