Description
Wise found out that Belle is not doing her job managing their video store Random Play, and instead she's doing something else. Turned out Belle is actually playing a brain game called Counting Queen, but with a special twist.
You are given an N×N chessboard that already has some queens on it. The already placed queens are in different rows. Place exactly one queen in every row that does not yet contain a queen, so that no two queens on the board attack each other. Two queens attack each other if they share a row, a column, or a diagonal. We guarantee that all the initally placed queens are valid
Your mission is to help Belle count how many different ways there are to do this, so she can go back to work and stop procrastinating. Two ways are different if at least one queen is placed in a different column.
To recall, a queen in chess can move horizontally, vertically, and diagonally. We want to count all possible number of ways to place the queens on the chessboard given that there is already some pre-placed queens
In the sample, we start with a 4×4 board and a pre-placed queen at (0,1), using zero-based coordinates. In row 1, the only safe position is (1,3). With these two queens in place, the only safe position in row 2 is (2,0). Finally, the queen in row 3 must be placed at (3,2).
This arrangement places exactly one queen in each row, with no two queens sharing a column or diagonal. It is the only valid completion that preserves the pre-placed queen, so the answer is 1.
Input
- The first line contains an integer N, the size of the grid. (1 ≤ N ≤ 12)
- The second line contains an integer K, the number of pre-placed queens. (0 ≤ K ≤ N)
- Each of the next K lines contains two integers r and c, the row and column of a pre-placed queen. (0 ≤ r, c < N)
Output
Print a single integer: the number of valid ways to place a queen in each remaining row.