Визначник булевої матриці

Вам надано останні $n-1$ рядків булевої матриці $A$ розміром $n\times n$. Ваше завдання — визначити булеві значення для першого рядка так, щоб $r=(\det (A)(\mathrm{mod}100003))$ було максимальним (див. примітки). Вам потрібно вивести лише значення $r$.

Вхідні дані

Перша строка містить ціле число $n(2\le n\le 400)$.

Рядки з $2$ по $n$ містять по $n$ чисел кожен: $i$-ий рядок містить числа (або $0$, або $1$) з $i$-го рядка матриці $A$.

Вихідні дані

Виведіть невід'ємне ціле число $r(0\le r<100003)$.

Приклади

$A$ є булевою матрицею тоді і тільки тоді, коли $A_{i,j}\in \{0,1\}$, $\forall A_{i,j}\in A$

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

де $M_{i,j}$ — матриця, отримана з $A$ видаленням рядка і стовпця, що містить $A_{i,j}$

$X(\mathrm{mod}B)$ = залишок від ділення $X$ на B.