{"raw_statement":[{"iden":"statement","content":"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.\n\nFrom 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: \n\nUnfortunately, 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.\n\nThe 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.\n\nEach 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.\n\nOutput 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.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input21 11 0Output1Input21 10 0Output0"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $, $ 1 \\leq N \\leq 10^3 $.  \nLet $ A \\in \\mathbb{Z}^{N \\times N} $ be given, with $ A_{i,j} \\in [0, 10^4] $.  \nLet $ M \\in \\{0,1\\}^{N \\times N} $ be an unknown binary matrix.  \n\nFor each $ i,j \\in \\{1, \\dots, N\\} $, define:  \n$$\nA_{i,j} = \\left( \\sum_{k=1}^N M_{i,k} \\right) + \\left( \\sum_{k=1}^N M_{k,j} \\right) - M_{i,j}\n$$\n\n**Constraints**  \nFor all $ i,j \\in \\{1, \\dots, N\\} $:  \n$$\nA_{i,j} = r_i + c_j - M_{i,j}\n$$  \nwhere $ r_i = \\sum_{k=1}^N M_{i,k} $ (row sum of row $ i $),  \nand $ c_j = \\sum_{k=1}^N M_{k,j} $ (column sum of column $ j $).  \n\nSince $ M_{i,j} \\in \\{0,1\\} $, it follows that:  \n$$\nM_{i,j} = r_i + c_j - A_{i,j} \\in \\{0,1\\}\n$$\n\nThus, for each $ i,j $:  \n$$\nr_i + c_j - A_{i,j} \\in \\{0,1\\}\n\\quad \\Rightarrow \\quad\nA_{i,j} \\in \\{r_i + c_j - 1, r_i + c_j\\}\n$$\n\nAdditionally, $ r_i = \\sum_{j=1}^N M_{i,j} = \\sum_{j=1}^N (r_i + c_j - A_{i,j}) $,  \nand similarly $ c_j = \\sum_{i=1}^N (r_i + c_j - A_{i,j}) $.\n\n**Objective**  \nCount the number of pairs $ (r_1, \\dots, r_N, c_1, \\dots, c_N) \\in \\mathbb{Z}^N \\times \\mathbb{Z}^N $ such that:  \n1. $ 0 \\leq r_i \\leq N $, $ 0 \\leq c_j \\leq N $ for all $ i,j $,  \n2. For all $ i,j $: $ r_i + c_j - A_{i,j} \\in \\{0,1\\} $,  \n3. $ r_i = \\sum_{j=1}^N (r_i + c_j - A_{i,j}) $ for all $ i $,  \n4. $ c_j = \\sum_{i=1}^N (r_i + c_j - A_{i,j}) $ for all $ j $.  \n\nThen, 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.","simple_statement":"Given an N×N matrix A, find how many 0-1 matrices M could produce A, where each A[i][j] is the sum of all 1s in row i and column j of M (counting M[i][j] only once).","has_page_source":false}