问题描述

#nck { width: 30px; height: auto; }

Snuke 收到了两个矩阵 $A$ 和 $B$ 作为生日礼物。每个矩阵都是一个 $N$ 行 $N$ 列的矩阵，只包含 $0$ 和 $1$。

然后他计算了两个矩阵的乘积，$C = AB$。由于他所有的计算都是在模二下进行的，所以 $C$ 也是一个 $N$ 行 $N$ 列的矩阵，只包含 $0$ 和 $1$。对于每个 $1 ≤ i, j ≤ N$，给定了 $c_{i,j}$，矩阵 $C$ 的第 $(i,j)$ 个元素。

然而，Snuke 不小心把矩阵 $A$ 和 $B$ 吃掉了，现在他只知道矩阵 $C$。计算可能的（有序）矩阵 $A$ 和 $B$ 的对数，对 $10^9+7$ 取模。

约束条件

• $1 ≤ N ≤ 300$
• $c_{i, j}$ 要么是 $0$，要么是 $1$。

输入

输入以以下格式从标准输入给出：

$N$

$c_{1, 1}$ $...$ $c_{1, N}$

:

$c_{N, 1}$ $...$ $c_{N, N}$

输出

打印两个矩阵 $A$ 和 $B$ 的可能的（有序）对数（对 $10^9+7$ 取模）。

输入示例1

2
0 1
1 0

输出示例1

6

输入示例2

10
1 0 0 1 1 1 0 0 1 0
0 0 0 1 1 0 0 0 1 0
0 0 1 1 1 1 1 1 1 1
0 1 0 1 0 0 0 1 1 0
0 0 1 0 1 1 1 1 1 1
1 0 0 0 0 1 0 0 0 0
1 1 1 0 1 0 0 0 0 1
0 0 0 1 0 0 1 0 1 0
0 0 0 1 1 1 0 0 0 0
1 0 1 0 0 1 1 1 1 1

输出示例2

741992411