/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
N 人の男性たちと N 人の女性たちがいます。 男性たちには 1, 2, \ldots, 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 組作ろうとしています。 このとき、各男性および各女性はちょうど 1 つのペアに属さなければなりません。
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 で割った余りを出力せよ。
入力例 1
3 0 1 1 1 0 1 1 1 1
出力例 1
3
ペアを作る方法は次の 3 通りです。 男性 i と女性 j のペアを (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 通りです。
- (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 で割った余りを出力することを忘れずに。
Score : 100 points
Problem Statement
There are N men and N women, both numbered 1, 2, \ldots, N.
For each i, j (1 \leq i, j \leq 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.
Constraints
- All values in input are integers.
- 1 \leq N \leq 21
- a_{i, j} is 0 or 1.
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}
Output
Print the number of ways in which Taro can make N pairs, modulo 10^9 + 7.
Sample Input 1
3 0 1 1 1 0 1 1 1 1
Sample Output 1
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 Input 2
4 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0
Sample Output 2
1
There is one way to make pairs, as follows:
- (1, 2), (2, 4), (3, 1), (4, 3)
Sample Input 3
1 0
Sample Output 3
0
Sample Input 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
Sample Output 4
102515160
Be sure to print the number modulo 10^9 + 7.