Жорстоке Бінго
Бінго — це популярна гра для вечірок, у якій беруть участь кілька гравців і один ведучий. Кожен гравець отримує картку бінго розміром N×N, що містить N^2 різних чисел (зазвичай N = 5). Ведучий по черзі витягує числа з лотереї. Коли число витягується, гравці відзначають відповідний квадрат на своїй картці, якщо це число там присутнє. Мета гри — першим відзначити N квадратів в одному вертикальному, горизонтальному або діагональному рядку і крикнути "Бінго!". Перемагає той, хто першим крикне "Бінго!".
У деяких випадках на картці може залишитися рівно N невідзначених квадратів або N(N-1) відзначених квадратів, але без бінго-візерунка. Ваше завдання — написати програму, яка підрахує кількість таких візерунків, які можна отримати з заданого початкового візерунка з нулем або більше відзначеними квадратами.
Вхідні дані
Вхід представлений у наступному форматі:
N K x_1 y_1 ... x_K y_K
Перша строка містить два числа: N (1 ≤ N ≤ 32) — розмір картки бінго, і K (0 ≤ K ≤ 8) — кількість відзначених квадратів у початковому візерунку. Далі слідують K строк, кожна з яких містить два числа x_i і y_i, що позначають, що квадрат у позиції (x_i, y_i) відзначений. Координати починаються з нуля (тобто 0 ≤ x_i, y_i ≤ N-1). Жодна пара відзначених квадратів не повторюється.
Вихідні дані
Виведіть кількість можливих небінго-візерунків з рівно N невідзначеними квадратами, які можна створити з даного початкового візерунка. Результат виведіть за модулем 10007 в одному рядку (оскільки число може бути дуже великим). Повернуті та дзеркально відображені візерунки вважаються різними і повинні враховуватися окремо.