题目描述

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

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

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

输入格式

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

$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

提示

制約

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