7287: AtCoder Educational DP Contest —— O - Matching
[Creator : ]
Description
There are $N$ men and $N$ women, both numbered $1,2,…,N$.
For each $i, j\ (1≤i,j≤N)$, the compatibility of Man $i$ and Woman $j$ is given as an integer $a_{i, j}$. If $a_{i, j} = 1$, Man $i$ and Woman $j$ are compatible; if $a_{i, j} = 0$, they are not.
Taro is trying to make $N$ pairs, each consisting of a man and a woman who are compatible. Here, each man and each woman must belong to exactly one pair.
Find the number of ways in which Taro can make $N$ pairs, modulo $10^9 + 7$.
For each $i, j\ (1≤i,j≤N)$, the compatibility of Man $i$ and Woman $j$ is given as an integer $a_{i, j}$. If $a_{i, j} = 1$, Man $i$ and Woman $j$ are compatible; if $a_{i, j} = 0$, they are not.
Taro is trying to make $N$ pairs, each consisting of a man and a woman who are compatible. Here, each man and each woman must belong to exactly one pair.
Find the number of ways in which Taro can make $N$ pairs, modulo $10^9 + 7$.
Input
Input is given from Standard Input in the following format:
$N$
$a_{1, 1}\ \ldots\ a_{1, N}$
$:$
$a_{N, 1}\ \ldots\ a_{N, N}$
$N$
$a_{1, 1}\ \ldots\ a_{1, N}$
$:$
$a_{N, 1}\ \ldots\ a_{N, N}$
Output
Print the number of ways in which Taro can make $N$ pairs, modulo $10^9 + 7$.
Constraints
All values in input are integers.
$1 \leq N \leq 21$
$a_{i, j}$ is 0 or 1.
$1 \leq N \leq 21$
$a_{i, j}$ is 0 or 1.
Sample 1 Input
3
0 1 1
1 0 1
1 1 1
Sample 1 Output
3
There are three ways to make pairs, as follows ((i, j) denotes a pair of Man i and Woman j):
- (1, 2), (2, 1), (3, 3)
- (1, 2), (2, 3), (3, 1)
- (1, 3), (2, 1), (3, 2)
Sample 2 Input
4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
Sample 2 Output
1
There is one way to make pairs, as follows:
- (1, 2), (2, 4), (3, 1), (4, 3)
Sample 3 Input
1
0
Sample 3 Output
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