← 返回题目列表

AtCoder · dp_o

O. 匹配

中文机器翻译题面 查看原题

分数: 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.