## Atcoder Educational DP Contest O - Matching

View as PDF

Points: 0.30 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Có ~N~ người đàn ông và ~N~ người phụ nữ đều được đánh số ~1,2,...,N~.

Với mỗi cặp số ~i,j~ ~(1 \le i,j \le N)~, độ hợp nhau của người đàn ông ~i~ và người phụ nữ ~j~ là ~a_{i,j}~. Nếu ~a_{i,j} = 1~ thì ông ~i~ và bà ~j~ hợp nhau, nếu ~a_{i,j} = 0 ~ thì ngược lại.

Taro tìm cách chia ~N~ người đàn ông và ~N~ người phụ nữ thành ~N~ cặp, trong đó mỗi cặp gồm một người đàn ông và một người phụ nữ hợp nhau.

Hãy tìm số cách khác nhau mà Taro có thể chia, modulo ~10^9+7~

#### Input

Dòng đầu tiên gồm số ~N~ ~(1 \le N \le 21)~.

~N~ dòng sau, mỗi dòng gồm ~N~ số nguyên ~0~ hoặc ~1~. Trong đó số thứ ~j~ ở hàng thứ ~i~ là giá trị của ~a_{i,j}~.

#### Output

In ra số cách chia cặp thỏa mãn, modulo ~10^9+7~

#### Sample 1

##### Input
3
0 1 1
1 0 1
1 1 1


#### Output

3


Có 3 cách thỏa mãn như sau (~(i,j)~ ký hiệu cho cặp giữa ông ~i~ và bà ~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


#### Output

1


Có 1 cách thỏa mãn như sau

• ~(1,2),(2,4),(3,1),(4,3)~

#### Sample 3

##### Input
1
0

##### Output
0


#### Sample 4

##### Input
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

##### Output
102515160


Lưu ý kết quả cần phải được in ra theo modulo ~10^9+7~.