P3182 [HAOI2016] Placing Pieces

Given an $N\times N$ matrix. Each row contains exactly one obstacle; it is guaranteed that no two obstacles are in the same row or the same column. You need to place $N$ pieces on this matrix (you cannot place a piece on a cell with an obstacle) such that each row contains exactly one piece and each column contains exactly one piece. Find the number of valid arrangements.

The first line contains an integer $N$, followed by an $N \times N$ matrix. $N\leq 200$. $0$ denotes no obstacle, and $1$ denotes an obstacle.

A single integer, the number of valid arrangements.

Translated by ChatGPT 5