Розстановка турів#3699
Потрібно визначити кількість способів розмістити тур на шаховій дошці розміром N \times N так, щоб у кожному рядку і стовпці була не більше однієї тури. Деякі клітини дошки можуть бути недоступними для розміщення тур.
У першому рядку подано число (1 \le N \le 3000). Далі йдуть рядків, кожен з яких містить символів, що описують дозволені клітини. Якщо туру можна поставити в клітину, відповідний символ — '1', інакше — '0'.
Оскільки відповідь може бути дуже великою, виведіть одне число — залишок від ділення знайденої кількості на .
Приклад 1