#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

The 8 Queens problem is a classic problem of placing 8 Queens on a 8x8 chess board such that no two Queens can attack each other. In short, the 8 Queens must be placed such that no two of them lie in the same row, column or diagonal. The image below shows 1 possible solution.

We count rotations and reflections as different solutions so for the 8 Queens problem, it is known that there are 92 solutions. Since I've already told you this answer, we shall make the problem more general. The problem will be generalised to the *N* queens problem on an *NxN* chess board. To make things more interesting, there will be *Q* queens initially placed on the chess board and *B* squares that cannot have queens placed on them. Count the number of solutions to the N queens problem satisfying all the above restrictions.

## Limits

For all test cases, 0 ≤ *Q,B* ≤ *N ^{2}*

Subtask 1 (7%): 1 ≤ *N* ≤ 4

Subtask 2 (11%): *N* = 8

Subtask 3 (14%): *N* = 10

Subtask 4 (19%): *N* = 12

Subtask 5 (22%): *N* = 13

Subtask 6 (26%): *N* = 14

Subtask 7 (0%): 15 ≤ *N* ≤ 16

Subtask 8 (1%): 1 ≤ *N* ≤ 20, *Q*=0, B=0

## Input

The first line of input will consist of a single integer *N*. The next line of input will consist of a single integer *Q* and the next *Q* lines will contain two integers 1 ≤ *X,Y* ≤ *N* that means that there is queen initially placed on the *X*th row and *Y*th column. The next line of input will consist of a single integer *B* and the next *B* lines will contain two integers 1 ≤ *X,Y* ≤ *N* that means that there cannot be a queen placed on the *X*th row and *Y*th column.

## Output

The output should only be a single integer representing the number of different solutions satisfying the restrictions given. Note that rotations and reflections are considered distinct solutions, and that it is possible that no solutions exist given the restrictions.

## Sample Input

8 0 0

## Sample Output

92

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 7 | 10 | 1s | 32MB | Minimum |

2 | 11 | 15 | 1s | 32MB | Minimum |

3 | 14 | 15 | 1s | 32MB | Minimum |

4 | 19 | 20 | 1s | 32MB | Minimum |

5 | 22 | 20 | 1s | 32MB | Minimum |

6 | 26 | 20 | 1s | 32MB | Minimum |

7 | 0 | 6 | 1s | 32MB | Minimum |

8 | 1 | 20 | 1s | 32MB | Average |

### Judge Compile Command

g++-7 ans.cpp -o nqueens -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512