Жорстоке Бінго#3550

Жорстоке Бінго

8 секунд

32 мегабайти

Дуже складна

Бінго — це популярна гра для вечірок, у якій беруть участь кілька гравців і один ведучий. Кожен гравець отримує картку бінго розміром $N \times N$ N \times N, що містить $N^{2}$ N^2 різних чисел (зазвичай $N = 5$ N = 5). Ведучий по черзі витягує числа з лотереї. Коли число витягується, гравці відзначають відповідний квадрат на своїй картці, якщо це число там присутнє. Мета гри — першим відзначити $N$ квадратів в одному вертикальному, горизонтальному або діагональному рядку і крикнути "Бінго!". Перемагає той, хто першим крикне "Бінго!".

У деяких випадках на картці може залишитися рівно $N$ невідзначених квадратів або $N (N - 1)$ N(N-1) відзначених квадратів, але без бінго-візерунка. Ваше завдання — написати програму, яка підрахує кількість таких візерунків, які можна отримати з заданого початкового візерунка з нулем або більше відзначеними квадратами.

Вхідні дані

Вхід представлений у наступному форматі:

$N$ $K$ $x_{1}$ x_1 $y_{1}$ y_1 ... $x_{K}$ x_K $y_{K}$ y_K

Перший рядок містить два числа: $N$ ( $1 \leq N \leq 32$ 1 \le N \le 32) — розмір картки бінго, і $K$ ( $0 \leq K \leq 8$ 0 \le K \le 8) — кількість відзначених квадратів у початковому візерунку. Далі слідують $K$ рядків, кожен з яких містить два числа $x_{i}$ x_i і $y_{i}$ y_i, що позначають, що квадрат у позиції ( $x_{i}$ x_i, $y_{i}$ y_i) відзначений. Координати починаються з нуля (тобто $0 \leq x_{i}, y_{i} \leq N - 1$ 0 \le x_i, y_i \le N-1). Жодна пара відзначених квадратів не повторюється.

Вихідні дані

Виведіть кількість можливих небінго-візерунків з рівно $N$ невідзначеними квадратами, які можна створити з даного початкового візерунка. Результат виведіть за модулем $10007$ в одному рядку (оскільки число може бути дуже великим). Повернуті та дзеркально відображені візерунки вважаються різними і повинні враховуватися окремо.

Приклади

Приклад 1