Розстановка турів

Потрібно визначити кількість способів розмістити N тур на шаховій дошці розміром N×N так, щоб у кожному рядку і стовпці була не більше однієї тури. Деякі клітини дошки можуть бути недоступними для розміщення тур.

Вхідні дані

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

Вихідні дані

Оскільки відповідь може бути дуже великою, виведіть одне число — залишок від ділення знайденої кількості на 2.

Приклади