#AT15. Matching

Matching

[O] Matching(dp_o)

来源: AtCoder Educational DP Contest - Problem O 原题时限:2 秒 / 内存:1024 MB

题目描述

有 NN 位男士和 NN 位女士,均编号为 1,2,…,N1, 2, \ldots, N。

对于每对 i,ji, j(1≤i,j≤N1 \le i, j \le N),男士 ii 与女士 jj 的契合度由整数 ai,ja_{i,j} 给出:若 ai,j=1a_{i,j} = 1 表示二人可以配对,若 ai,j=0a_{i,j} = 0 表示不能配对。

太郎想组成 NN 对,每对由一位男士和一位可以与之配对的女士组成,且每位男士、每位女士都恰好属于一对。

求太郎组成 NN 对的不同方案数,对 109+710^9 + 7 取模。

输入格式

输入由标准输入按以下格式给出:

N
a_{1,1} a_{1,2} \ldots a_{1,N}
:
a_{N,1} a_{N,2} \ldots a_{N,N}

输出格式

输出方案数对 109+710^9 + 7 取模的结果。

数据范围

  • 输入中的所有值均为整数。
  • 1≤N≤211 \le N \le 21
  • ai,ja_{i,j} 为 00 或 11。

样例 1

输入:

3
0 1 1
1 0 1
1 1 1

输出:

3

样例 2

输入:

4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

输出:

1

样例 3

输入:

1
0

输出:

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

输出:

102515160