{"raw_statement":[{"iden":"statement","content":"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$. \n\nThe $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$. \n\nHowever, there are k pairs of students that cannot be paired together to avoid trouble in the classroom.\n\nYou 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.\n\nThe 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.\n\nEach 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.\n\nOutput the number of ways modulo $10^9 + 7$, on a single line.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"Output the number of ways modulo $10^9 + 7$, on a single line."},{"iden":"examples","content":"Input2 1 0\nOutput2\nInput2 1 1\n1 2\nOutput1\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, e, k \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 2000 $, $ 0 \\leq e \\leq 4 $, $ 0 \\leq k \\leq 2000 $.  \nLet $ A = \\{1, 2, \\dots, n\\} $ be the set of students in the first line.  \nLet $ B = \\{1, 2, \\dots, n\\} $ be the set of students in the second line.  \nLet $ E \\subseteq A \\times B $ be the set of allowed pairs:  \n$$ E = \\{ (i, j) \\in A \\times B \\mid |i - j| \\leq e \\} $$  \nLet $ F \\subseteq A \\times B $ be the set of forbidden pairs, with $ |F| = k $, and $ F \\cap E = \\emptyset $ (given as input).  \nDefine the set of valid pairs:  \n$$ P = E \\setminus F $$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2000 $  \n2. $ 0 \\leq e \\leq 4 $  \n3. $ 0 \\leq k \\leq 2000 $  \n4. For each $ (u_i, v_i) \\in F $, $ 1 \\leq u_i, v_i \\leq n $  \n5. All forbidden pairs are distinct and satisfy $ |u_i - v_i| \\leq e $ (since otherwise they wouldn't be in $ E $ to begin with)  \n\n**Objective**  \nCompute 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 $.  \nOutput the result modulo $ 10^9 + 7 $.","simple_statement":"You have two lines of n students each.  \nStudent i in the first line can only pair with student j in the second line if |i - j| ≤ e.  \nThere are k forbidden pairs that cannot be matched.  \nCount the number of ways to pair all students into n valid pairs (each student in exactly one pair), modulo 10^9 + 7.","has_page_source":false}