Matching

题意翻译

给定二分图，两个集合都有 $N$ 个点，$a_{i,j}=1$ 表示第一个集合第 $i$ 个点与第二个集合第 $j$ 个点连边。 求二分图完备匹配数，答案对 $10^9+7$ 取模。

题目描述

[problemUrl]: https://atcoder.jp/contests/dp/tasks/dp_o $ 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 $ で割った余りを出力せよ。

输入输出样例

输入样例 #1

3
0 1 1
1 0 1
1 1 1

输出样例 #1

3

输入样例 #2

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

输出样例 #2

1

输入样例 #3

1
0

输出样例 #3

0

输入样例 #4

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

输出样例 #4

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 $ で割った余りを出力することを忘れずに。