题号：NC224091
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Goodeat gets a matrix of N * N. We use (x,y) to denote the entry in the x-th row and the y-th column (
).
Now Goodeat wants to choose C entries, and the following conditions must be met:
1. In each row, at least one entry is chosen
2. In each column, at least one entry is chosen
3. On the diagonal line (that is, all the entries satisfying x=y), at least one entry is chosen
4. On the negative diagonal (that is, all the entries satisfying x+y=N+1), at least one entry is chosen
Now Goodeat wants to choose C entries, and the following conditions must be met:
1. In each row, at least one entry is chosen
2. In each column, at least one entry is chosen
3. On the diagonal line (that is, all the entries satisfying x=y), at least one entry is chosen
4. On the negative diagonal (that is, all the entries satisfying x+y=N+1), at least one entry is chosen
There are K entries that can’t be chosen.
Now Goodeat wants to know about the number of ways for choosing entries. Since the number may be too large, you only need to output the answer modulo 10007.
输入描述:
The first line contains three integers.
In the next K lines, each line contains two positive integers x, y, which means the entry (x, y) cannot be chosen.
It's guaranteed that each entry is given at most once.
输出描述:
Output a single integer denoting the answer.