#173. Ghép cặp (MATCHING)

Có người đàn ông và người phụ nữ, được đánh số từ đến . Bạn được cho một ma trận tương hợp . Nếu , người đàn ông thứ và người phụ nữ thứ là tương hợp; nếu , họ không tương hợp. Tìm số cách để tạo ra cặp đôi, mỗi cặp gồm một người đàn ông và một người phụ nữ, sao cho tất cả mọi người đều được ghép cặp và trong mỗi cặp, hai người phải tương hợp với nhau. In kết quả theo modulo .

Dữ liệu:

• Dòng đầu tiên chứa số nguyên .
• dòng tiếp theo, mỗi dòng chứa số nguyên .

Kết quả: In ra số cách ghép cặp, modulo .

Ví dụ:

Dữ liệu:

3
1 1 1
1 1 1
1 1 1

Kết quả:

6

Giới hạn:

• là hoặc .