Problem C
Holey N-Queens (Batman)

The $N$-queens problem is the problem of placing $N$ queens on a $N \times N$ chessboard so that no queen shares a row, column or a diagonal with any other queen. Essentially, we are trying to place the queens without any queen threatening another. For example, the first image below (without holes in the board) is a solution to the $8$-queens problem.

For this problem, consider the problem we’ll call the ‘holey $N$-queens problem’. Instead of having an everyday chessboard (of arbitrary size), your chessboard is like the second image above (without queens): it has holes through some of the squares. You can’t place a queen on a square that has a hole, but a queen can threaten another even if there is a hole on the path between them. Given a holey chessboard, you must find placements for the $N$ queens so that no queen threatens another. The third image above (with holes and queens) shows one such solution.

Input

Input consists of up to $1\, 000$ board descriptions. Each description starts with a line containing a pair of integers, $3 \le N \le 12$ and $0 \le M \le N^2$, indicating respectively the size of one side of the board, and the number of holes. The next $M$ lines each describe the location of a unique hole in the board. A hole is described by its row and column, each in the range $[0,N-1]$. The end of input is marked by values of zero for $N$ and $M$.

Output

For each problem description, print out the number of unique $N$-queens solutions that are possible. Two solutions are considered different if any space is occupied by a queen in one solution but not in the other.

8 0
8 3
0 3
5 4
3 7
0 0

92
50