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

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

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

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

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

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

Примеры