Description

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.

Input Format

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.

Output Format

A single integer, the number of valid arrangements.

2
0 1
1 0

1

Hint

Translated by ChatGPT 5