比赛_信奥算法提高+/省选--ACGO题库

题目描述

有 $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$ ，则匹配不好。

NoonMaple想要将所有匹配良好的男女分别配对，组成 $N$ 对。每个男生和每个女生都必须恰好属于一对。

请问有多少种组成 $N$ 对的方法？请输出对 $10^9 + 7$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$
$a_{1, 1}\ a_{1, 2}\ \ldots\ a_{1, N}$
$a_{2, 1}\ a_{2, 2}\ \ldots\ a_{2, N}$
$\vdots$
$a_{N, 1}\ a_{N, 2}\ \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

组成配对的方法有以下 $3$ 种。用 $(i, j)$ 表示男性 $i$ 和女性 $j$ 的配对。

$(1, 2),\ (2, 1),\ (3, 3)$
$(1, 2),\ (2, 3),\ (3, 1)$
$(1, 3),\ (2, 1),\ (3, 2)$

样例解释 2

组成配对的方法有以下 $1$ 种。

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

样例解释 4

不要忘记输出对 $10^9 + 7$ 取模的结果。

数据范围

所有输入均为整数。
$1 \leq N \leq 21$
$a_{i, j}$ 仅为 $0$ 或 $1$ 。

A75070.比赛