405922: GYM102157 3 Perfect Matching

There is a class of $$$2*n$$$ students, and the teacher wants all of them to get matched into $$$n$$$ pairs. She divides the students into two lines of length $$$n$$$, and numbers the students in both lines from $$$1$$$ to $$$n$$$.

The $$$i_{th}$$$ numbered student in the first line can be partnered with the $$$j_{th}$$$ numbered student in the second line if $$$|i-j| \leq e$$$.

However, there are k pairs of students that cannot be paired together to avoid trouble in the classroom.

You need to print the number of ways you can match the students into $$$n$$$ pairs such that the constraints above are met. One way is different than the other if at least one student has a different partner.

The first line contains $$$3$$$ integers $$$n$$$, $$$e$$$, $$$k$$$ $$$(1 \leq n \leq 2000,0 \leq e \leq 4, 0 \leq k \leq 2000)$$$,the number of students 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 \leq u_i,v_i \leq n)$$$,the number of the student from the first line and the number of the student from the second line that cannot be matched together respectively. No pair of students 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