Жестокое Бинго
Бинго — это популярная игра для вечеринок, в которой участвуют несколько игроков и один ведущий. Каждый игрок получает карточку бинго размером 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 в одной строке (так как число может быть очень большим). Повернутые и зеркально отраженные узоры считаются разными и должны учитываться отдельно.