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_{t h}$ numbered student in the first line can be partnered with the $j_{t h}$ numbered student in the second line if $| i -j | <= 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 <= n <= 2000, 0 <= e <= 4, 0 <= k <= 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 <= u_i, v_i <= 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.
## Input
The first line contains $3$ integers $n$, $e$, $k$ $(1 <= n <= 2000, 0 <= e <= 4, 0 <= k <= 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 <= u_i, v_i <= 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
Output the number of ways modulo $10^9 + 7$, on a single line.
[samples]
**Definitions**
Let $ n, e, k \in \mathbb{Z} $ with $ 1 \leq n \leq 2000 $, $ 0 \leq e \leq 4 $, $ 0 \leq k \leq 2000 $.
Let $ A = \{1, 2, \dots, n\} $ be the set of students in the first line.
Let $ B = \{1, 2, \dots, n\} $ be the set of students in the second line.
Let $ E \subseteq A \times B $ be the set of allowed pairs:
$$ E = \{ (i, j) \in A \times B \mid |i - j| \leq e \} $$
Let $ F \subseteq A \times B $ be the set of forbidden pairs, with $ |F| = k $, and $ F \cap E = \emptyset $ (given as input).
Define the set of valid pairs:
$$ P = E \setminus F $$
**Constraints**
1. $ 1 \leq n \leq 2000 $
2. $ 0 \leq e \leq 4 $
3. $ 0 \leq k \leq 2000 $
4. For each $ (u_i, v_i) \in F $, $ 1 \leq u_i, v_i \leq n $
5. All forbidden pairs are distinct and satisfy $ |u_i - v_i| \leq e $ (since otherwise they wouldn't be in $ E $ to begin with)
**Objective**
Compute the number of perfect matchings from $ A $ to $ B $ using only pairs in $ P $, i.e., the number of bijections $ f: A \to B $ such that $ (i, f(i)) \in P $ for all $ i \in A $.
Output the result modulo $ 10^9 + 7 $.