잔인한 빙고

빙고는 여러 명의 플레이어와 한 명의 진행자가 함께하는 파티 게임이다. 각 플레이어는 N × N 격자에 N2개의 서로 다른 숫자가 적힌 빙고 카드를 받는다(보통 N = 5). 게임이 진행되는 동안 진행자는 추첨기에서 숫자를 하나씩 뽑는다. 숫자가 뽑힐 때마다 플레이어는 카드에 그 숫자가 있으면 해당 칸을 표시한다. 플레이어의 목표는 가로, 세로, 대각선 중 한 줄에 있는 N개의 칸을 모두 표시한 뒤 "빙고!"를 외치는 것이다. 가장 먼저 "빙고!"를 외친 플레이어가 게임에서 이긴다.

아주 불운한 경우, 카드에 표시되지 않은 칸이 정확히 N개 있거나, 표시된 칸이 N(N-1)개 있으면서 빙고 줄이 하나도 없을 수 있다. 이 문제에서 여러분이 할 일은, 표시된 칸이 0개 이상 있는 초기 상태가 주어졌을 때 그러한 패턴이 몇 가지 가능한지 세는 프로그램을 작성하는 것이다.

입력은 다음과 같은 형식으로 주어진다.

N K
x1 y1
.
.
.
xK yK

첫 줄에는 빙고 카드의 크기 N (1 ≤ N ≤ 32)과 초기 상태에서 표시된 칸의 수 K (0 ≤ K ≤ 8)가 주어진다. 이어서 K개의 줄이 주어지며, 각 줄에는 좌표 (xi, yi)에 있는 칸이 표시되었음을 나타내는 두 수 xi와 yi가 있다. 좌표는 0부터 시작한다(즉, 0 ≤ xi, yi ≤ N - 1). 표시된 두 칸이 같은 경우는 없다.

주어진 초기 상태에서 만들 수 있는, 표시되지 않은 칸이 정확히 N개인 빙고가 아닌 패턴의 수를 10007로 나눈 나머지를 한 줄에 출력한다(수가 매우 클 수 있기 때문이다). 회전하거나 뒤집은 패턴은 서로 다른 것으로 보고 각각 센다.