You are given the last n−1 rows of an n×n boolean matrix A. Your task is to determine boolean values for the first row such that r=(det(A)(mod100003)) is maximized (see notes). You only need to output the value of r.
The first line contains integer n (2≤n≤400).
Lines 2 through n contain n numbers each: i−th line containing the numbers (either 0 or 1) in the i−th row of A.
Output non-negative integer r (0≤r<100003) on the single line.
A is a boolean matrix iff Ai,j∈{0,1}, ∀Ai,j∈A
The determinant of an n×n matrix A, denoted det(A), is a scalar that is defined inductively as:
det(A)={A1,1∑j(−1)1+jA1,jdet(M1,j)if n=1if n>1
Where Mi,j is the matrix obtained from A by deleting the row and column containing Ai,j
X(modB) = The remainder of division of X by B.