# Problem J: Cruel Bingo

Bingo is a party game played by many players and one game master. Each player is given a bingo card containing *N*^{2} different numbers in a *N* × *N* grid (typically *N* = 5). The master draws numbers from a lottery one by one during the game. Each time a number is drawn, a player marks a square with that number if it exists. The playerfs goal is to have *N* marked squares in a single vertical, horizontal, or diagonal line and then call gBingo!h The first player calling gBingo!h wins the game.

In ultimately unfortunate cases, a card can have exactly *N* unmarked squares, or *N*(*N*-1) marked squares, but not a bingo pattern. Your task in this problem is to write a program counting how many such patterns are possible from a given initial pattern, which contains zero or more marked squares.

## Input

The input is given in the following format:

*N K*

*x*_{1} *y*_{1}

.

.

.

*x*_{K} y_{K}

The input begins with a line containing two numbers *N* (1 ≤ *N* ≤ 32) and *K* (0 ≤ *K* ≤ 8), which represent the size of the bingo card and the number of marked squares in the initial pattern respectively.
Then *K* lines follow, each containing two numbers *x*_{i} and *y*_{i} to indicate the square at (*x*_{i}, *y*_{i}) is marked. The coordinate values are zero-based (i.e. 0 ≤ *x*_{i}, *y*_{i} ≤ *N* - 1). No pair of marked squares coincides.

## Output

Count the number of possible non-bingo patterns with exactly *N* unmarked squares that can be made from the given initial pattern, and print the number in modulo 10007 in a line (since it is supposed to be huge). Rotated and mirrored patterns should be regarded as different and counted each.

## Sample Input 1

4 2
0 2
3 1

## Output for the Sample Input 1

6

## Sample Input 2

4 2
2 3
3 2

## Output for the Sample Input 2

6

## Sample Input 3

10 3
0 0
4 4
1 4

## Output for the Sample Input 3

1127