Задачі
Расстановка ладей
Расстановка ладей
Требуется посчитать количество способов расставить \textbf{N} ладей на шахматной доске размером \textbf{N}×\textbf{N} так, чтобы на каждой горизонтали и вертикали было не более одной фигуры. При этом на некоторые клетки доски ладьи ставить нельзя.
\InputFile
В первой строке записано число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{3000}). Далее записаны \textbf{N} строк, в каждой из которых по \textbf{N} символов--- описание разрешённых клеток. Если в клетку можно ставить ладью, то соответствующий символ равен '\textbf{1}', иначе --- '\textbf{0}'.
\includegraphics{file:///C:/Temp/moz-screenshot.png}
\includegraphics{file:///C:/Temp/moz-screenshot-1.png}
\OutputFile
Так как ответ может быть очень большим, выведите одно число --- остаток от деления искомого количества на \textbf{2}.
Вхідні дані #1
3 111 011 101
Вихідні дані #1
1