配点 : $100$ 点

問題文

$N$ 人の男性たちと $N$ 人の女性たちがいます。 男性たちには $1, 2, \ldots, N$ と番号が振られています。 同様に、女性たちには $1, 2, \ldots, N$ と番号が振られています。

各 $i, j$ ($1 \leq i, j \leq N$) について、男性 $i$ と女性 $j$ の相性の良し悪しが整数 $a_{i, j}$ によって与えられます。 $a_{i, j} = 1$ ならば男性 $i$ と女性 $j$ は相性が良く、$a_{i, j} = 0$ ならば相性が悪いです。

太郎君は、相性が良い男女どうしのペアを $N$ 組作ろうとしています。 このとき、各男性および各女性はちょうど $1$ つのペアに属さなければなりません。

$N$ 組のペアを作る方法は何通りでしょうか？ $10^9 + 7$ で割った余りを求めてください。

制約

• 入力はすべて整数である。
• $1 \leq N \leq 21$
• $a_{i, j}$ は $0$ または $1$ である。

入力

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

$N$

$a_{1, 1}$ $\ldots$ $a_{1, N}$

$:$

$a_{N, 1}$ $\ldots$ $a_{N, N}$

出力

$N$ 組のペアを作る方法は何通りか？ $10^9 + 7$ で割った余りを出力せよ。

3
0 1 1
1 0 1
1 1 1

3

ペアを作る方法は次の $3$ 通りです。 男性 $i$ と女性 $j$ のペアを $(i, j)$ で表します。

• $(1, 2), (2, 1), (3, 3)$
• $(1, 2), (2, 3), (3, 1)$
• $(1, 3), (2, 1), (3, 2)$

4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

1

ペアを作る方法は次の $1$ 通りです。

• $(1, 2), (2, 4), (3, 1), (4, 3)$

1
0

0

21
0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1
1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0
0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1
0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0
1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0
0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1
0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1
0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1
0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0
0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1
0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1
1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1
0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1
1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1
0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1
0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0
1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0
1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0

102515160

答えを $10^9 + 7$ で割った余りを出力することを忘れずに。