AT_dp_o Matching

有 $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$ 对。每个男性和每个女性都必须恰好属于一对。 请问有多少种组成 $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 \leq N \leq 21$ - $a_{i, j}$ 仅为 $0$ 或 $1$。 ## 样例解释 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$ 取模的结果。 由 ChatGPT 4.1 翻译