问题陈述

有 $N$ 名男性和 $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$ 。

限制因素

• 所有输入值均为整数。
• $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

成对的方法有以下三种（ $(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, 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$ 的模数。

来源

https://atcoder.jp/contests/dp/tasks/dp_o