分数: 100 点
问题陈述
有 N 男人和 N 女性,均编号 1, 2, \ldots, N.
对于每个 i, j (1 \leq i, j \leq N),Man的兼容性 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} is 0 or 1.
输入
输入由标准输入按以下格式给出:
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
配对的方式有以下三种((i, j) 表示一对 Man i 和女人 j):
- (1, 2), (2, 1), (3, 3)
- (1, 2), (2, 3), (3, 1)
- (1, 3), (2, 1), (3, 2)
示例输入 2
4 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0
示例输出 2
1
有一种配对方法,如下所示:
- (1, 2), (2, 4), (3, 1), (4, 3)
示例输入 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
请务必打印模数 10^9 + 7.