You are given an $N \times N$ matrix. Each row contains one obstacle, and it is guaranteed that no two obstacles are in the same row and no two obstacles are in the same column. You are required to place $N$ chess pieces on this matrix (pieces cannot be placed on the positions of obstacles) such that there is exactly one piece in each row and exactly one piece in each column. Find the number of valid ways to do this.

Input

The first line contains an integer $N$, followed by an $N \times N$ matrix.

Output

A single integer representing the number of valid ways.

Constraints

• $20\%$ of the data guarantees: $N \le 10$
• $60\%$ of the data guarantees: $N \le 20$
• $100\%$ of the data guarantees: $N \le 200$

Examples

Input 1

2
0 1
1 0

Output 1

1