Determinant of boolean matrix

Input

The first line contains integer $n (2 \leq n \leq 400)$ n~(2 \leq n \leq 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 \leq r < 100003)$ r~(0 \le r < 100003) on the single line.

Examples

Example 1

Loading

Example 2

Loading

Note

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

$det (A) = {A_{1, 1} \sum_{j} (- 1)^{1 + j} A_{1, j} det (M_{1, j}) if n = 1 if n > 1$ \det(A) = \begin{cases} A_{1,1} \qquad &\text{if }\ n = 1 \\ \sum_j(-1)^{1+j}A_{1,j}\det(M_{1,j})&\text{if }\ n > 1 \end{cases}

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

$X (mod B)$ X \pmod B = The remainder of division of $X$ by $B$ .