题目描述

$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$ で割った余りを求めてください。

输入格式

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

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

输出格式

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

题目大意

给定二分图，两个集合都有 $N$ 个点，$a_{i,j}=1$ 表示第一个集合第 $i$ 个点与第二个集合第 $j$ 个点连边。

求二分图完备匹配数，答案对 $10^9+7$ 取模。

3
0 1 1
1 0 1
1 1 1

3

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

1

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

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

ペアを作る方法は次の $1$ 通りです。 - $(1,\ 2),\ (2,\ 4),\ (3,\ 1),\ (4,\ 3)$

Sample Explanation 4

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