404348: GYM101484 I Matrix Sum

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 ≤ 10³), 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 A_ij (0 ≤ A_ij ≤ 10⁴) 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.

2
1 1
1 0

1

2
1 1
0 0

0