Bingo is a party game played by many players and one game master. Each player is given a bingo card containing \textbf{N^2} different numbers in a \textbf{N}×\textbf{N} grid (typically \textbf{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 player’s goal is to have \textbf{N} marked squares in a single vertical, horizontal, or diagonal line and then call "\textit{Bingo!}" The first player calling "\textit{Bingo!}" wins the game. In ultimately unfortunate cases, a card can have exactly \textbf{N} unmarked squares, or \textbf{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. \InputFile The input is given in the following format: \textbf{N K x_1 y_1 ... x_K y_K} The input begins with a line containing two numbers \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{32}) and \textbf{K} (\textbf{0} ≤ \textbf{K} ≤ \textbf{8}), which represent the size of the bingo card and the number of marked squares in the initial pattern respectively. Then \textbf{K} lines follow, each containing two numbers \textbf{x_i} and \textbf{y_i} to indicate the square at (\textbf{x_i}, \textbf{y_i}) is marked. The coordinate values are zero-based (i.e. \textbf{0} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{N-1}). No pair of marked squares coincides. \OutputFile Count the number of possible non-bingo patterns with exactly \textbf{N} unmarked squares that can be made from the given initial pattern, and print the number in modulo \textbf{10007} in a line (since it is supposed to be huge). Rotated and mirrored patterns should be regarded as different and counted each.