[Drob29]

мне нужно решить одну задачку:
У Серёжи есть шахматная доска n на n клеток и много ладей. Он уже расставил на ней несколько ладей так, что они не бьют друг друга (напоминаем, что шахматная ладья бьет все клетки, находящиеся с ней на одной вертикали или одной горизонтали). Теперь он хочет поставить еще несколько ладей так, чтобы по прежнему никакая ладья не била другую. Кроме того, каждая клетка поля должна либо биться какой-то ладьей, либо на ней должна стоять ладья. Серёжу интересует вопрос, а сколькими способами он может это сделать?

Формат файла входных данных:
Сначала даны два числа n и k (1 <= n <= 12, 0 <= k <= n) - размер доски и количество ладей, уже стоящих на поле.
В следующих k строках по два числа: номер вертикали и номер горизонтали, на пересечении которых стоит очередная ладья. Гарантируется, что ладьи не бьют друг друга.

Формат файла выходных данных:
Выведите одно число - количество способов доставить еще ладей так, чтобы указанные условия были выполнены

Комментарий:
В первом примере ладьи стоят в левом нижнем и правом верхнем углах. Тогда получить требуемый результат можно поставив ладьи либо на поля с координатами (2, 2) и (3, 3), либо на (2, 3) и (3, 2).
Во втором примере ладьи уже бьют все клетки, поэтому существует единственный способ - ничего не делать.