eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Расстановка ладей

Расстановка ладей

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Требуется посчитать количество способов расставить N ладей на шахматной доске размером N×N так, чтобы на каждой горизонтали и вертикали было не более одной фигуры. При этом на некоторые клетки доски ладьи ставить нельзя.

Входные данные

В первой строке записано число N (1N3000). Далее записаны N строк, в каждой из которых по N символов— описание разрешённых клеток. Если в клетку можно ставить ладью, то соответствующий символ равен '1', иначе — '0'.

Выходные данные

Так как ответ может быть очень большим, выведите одно число — остаток от деления искомого количества на 2.

Пример

Входные данные #1
3
111
011
101
Выходные данные #1
1
Источник III Международная Летняя школа программирования 2012 г. Севастополь