Consider an N-by-N chessboard and N pieces of castles. Your task is to find the number of possible ways to put the N castles on the chessboard such that there are no conflicts between any castles. The chessboard consists of K broken grids and you cannot put the castles on those grids.
For example, if N=3, K=2, and the broken grids are (0,0) and (0,2), then your answer is 2 because there are only two feasible solutions:
x#-
#--
x-#
x-#
#--
x#-
The first line of the input is an integer indicating the number N of castles.
The second line contains an integer indicating the number K of broken grids.
Each of the following K lines contains a pair of integers indicating the position (row, column) of one of the K broken grids. N < 30 and K < N*N.
The index for row and column starts from 0.
The number of feasible solutions.