Sancho is a matrix lover. Today he decided to play with a square matrix M with N rows and N columns. Every cell i, j of this matrix contains either 0 or 1.
From this matrix M he created another matrix A. Every cell i, j in this new matrix A contains the sum of the values of the cells in M that are in row i or column j. The element in the cell i, j of the matrix M should be added only once. Formally:
Unfortunately, Sancho lost the original matrix M and now, having only matrix A, he wonders what is the number of matrices M, such that matrix A can be created from M.
The first line of the input contains a single integer N (1 ≤ N ≤ 103), indicating the number of rows and columns of matrices M and A.
Each of the next N lines contains N integers. The j-th element of the i-th line Aij (0 ≤ Aij ≤ 104) is the value of the cell i, j of matrix A.
Output a single integer: the number of matrices M that could have been used to create the matrix A when the process described above is followed.
## Input
The first line of the input contains a single integer N (1 ≤ N ≤ 103), indicating the number of rows and columns of matrices M and A.Each of the next N lines contains N integers. The j-th element of the i-th line Aij (0 ≤ Aij ≤ 104) is the value of the cell i, j of matrix A.
## Output
Output a single integer: the number of matrices M that could have been used to create the matrix A when the process described above is followed.
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $, $ 1 \leq N \leq 10^3 $.
Let $ A \in \mathbb{Z}^{N \times N} $ be given, with $ A_{i,j} \in [0, 10^4] $.
Let $ M \in \{0,1\}^{N \times N} $ be an unknown binary matrix.
For each $ i,j \in \{1, \dots, N\} $, define:
$$
A_{i,j} = \left( \sum_{k=1}^N M_{i,k} \right) + \left( \sum_{k=1}^N M_{k,j} \right) - M_{i,j}
$$
**Constraints**
For all $ i,j \in \{1, \dots, N\} $:
$$
A_{i,j} = r_i + c_j - M_{i,j}
$$
where $ r_i = \sum_{k=1}^N M_{i,k} $ (row sum of row $ i $),
and $ c_j = \sum_{k=1}^N M_{k,j} $ (column sum of column $ j $).
Since $ M_{i,j} \in \{0,1\} $, it follows that:
$$
M_{i,j} = r_i + c_j - A_{i,j} \in \{0,1\}
$$
Thus, for each $ i,j $:
$$
r_i + c_j - A_{i,j} \in \{0,1\}
\quad \Rightarrow \quad
A_{i,j} \in \{r_i + c_j - 1, r_i + c_j\}
$$
Additionally, $ r_i = \sum_{j=1}^N M_{i,j} = \sum_{j=1}^N (r_i + c_j - A_{i,j}) $,
and similarly $ c_j = \sum_{i=1}^N (r_i + c_j - A_{i,j}) $.
**Objective**
Count the number of pairs $ (r_1, \dots, r_N, c_1, \dots, c_N) \in \mathbb{Z}^N \times \mathbb{Z}^N $ such that:
1. $ 0 \leq r_i \leq N $, $ 0 \leq c_j \leq N $ for all $ i,j $,
2. For all $ i,j $: $ r_i + c_j - A_{i,j} \in \{0,1\} $,
3. $ r_i = \sum_{j=1}^N (r_i + c_j - A_{i,j}) $ for all $ i $,
4. $ c_j = \sum_{i=1}^N (r_i + c_j - A_{i,j}) $ for all $ j $.
Then, for each such valid $ (r, c) $, there is exactly one corresponding $ M $, so the total number of valid $ M $ is equal to the number of such valid $ (r, c) $ pairs.