Требуется посчитать количество способов расставить \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}.