Determinant of boolean matrix

You are given the last $n-1$ rows of an $n\times n$ boolean matrix $A$. Your task is to determine boolean values for the first row such that $r=(\det (A)(\mathrm{mod}100003))$ is maximized (see notes). You only need to output the value of $r$.

Input

The first line contains integer $n(2\le n\le 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

Output non-negative integer $r(0\le r<100003)$ on the single line.

Examples

$A$ is a boolean matrix iff $A_{i,j}\in \{0,1\}$, $\forall A_{i,j}\in A$

The determinant of an $n\times n$ matrix $A$, denoted $\det (A)$, is a scalar that is defined inductively as:

$\det (A)=\{\begin{array}{ll}{A}_{1,1}& \text{if }n=1\\ {\sum }_j(-1{)}^{1+j}{A}_{1,j}\det (M_{1,j})& \text{if }n>1\end{array}$

Where $M_{i,j}$ is the matrix obtained from $A$ by deleting the row and column containing $A_{i,j}$

$X(\mathrm{mod}B)$ = The remainder of division of $X$ by B.