406023: GYM102219 F Military Class

There is a military class of $$$2*n$$$ soldiers, and the commander wants all of them to get partnered into n pairs. He divides the soldiers into two lines of length $$$n$$$, and numbers the soldiers in both lines from $$$1$$$ to $$$n$$$.

The $$$i_{th}$$$ numbered soldiers in the first line can be partnered with the $$$j_{th}$$$ numbered soldiers in the second line if $$$|i - j| ≤ e$$$. However, there are $$$k$$$ pairs of soldiers that cannot be paired together. You need to print the number of ways you can match the soldiers into $$$n$$$ pairs such that the constraints above are met. One way is different than the other if at least one soldiers has a different partner.

The first line contains 3 integers $$$n, e, k (1 ≤ n ≤ 2000, 0 ≤ e ≤ 4, 0 ≤ k ≤ 2000)$$$, the number of soldiers in each line, the value that determines the range, and the number of invalid pairs, respectively.

Each of the next $$$k$$$ lines contains two integers $$$u_{i}, v_{i} (1 ≤ u_{i}, v_{i} ≤ n)$$$, the number of the soldiers from the first line and the number of the soldiers from the second line that cannot be matched together respectively. No pair of soldiers will appear twice in the input.

Output the number of ways modulo $$$10^{9} + 7$$$, on a single line.

2 1 0

2

2 1 1
1 2

1