Atcoder Educational DP Contest O - Matching

View as PDF

Submit solution


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~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.