配点 : $1500$ 点

問題文

すぬけ君は誕生日プレゼントとして二つの行列 $A$ と $B$ をもらいました。 それぞれの行列は $0$ と $1$ のみからなる $N$ 行 $N$ 列の行列です。

すぬけ君は、行列の積 $C = AB$ を計算しました。 全ての計算を modulo 2 で行ったので、 $C$ も $0$ と $1$ のみからなる $N$ 行 $N$ 列の行列です。 $1 \leq i, j \leq N$ について、行列 $C$ の $(i, j)$ 成分 $c_{i, j}$ が与えられます。

しかし、すぬけ君は間違って行列 $A$ と $B$ を食べてしまったので、$C$ のみを知っています。 (順序付きの) 行列の組 ($A$, $B$) が何通り考えられるか、modulo $10^9+7$ で求めてください。

制約

• $1 \leq N \leq 300$
• $c_{i, j}$ は $0$ または $1$ である

入力

入力は以下の形式で標準入力から与えられる。

$N$

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

:

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

出力

(順序付きの) 行列の組 ($A$, $B$) が何通り考えられるか、modulo $10^9+7$ で出力せよ。

2
0 1
1 0

6

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

741992411