Maximize Minimum Difference

**Note: The time limit for this problem is 4s, twice the default.**

Moo! You are given an integer $N$ ( $2 \leq N \leq 2000$ ). Consider all permutations $p = [p_{0}, p_{1}, \dots, p_{N - 1}]$ of $[0, 1, 2 \dots, N - 1]$ . Let $f (p) = min_{i = 0}^{N - 2} ∣ p_{i} - p_{i + 1} ∣$ denote the minimum absolute difference between any two consecutive elements of $p$ . and let $S$ denote the set of all $p$ that achieve the maximum possible value of $f (p)$ .

You are additionally given $K$ ( $0 \leq K \leq N$ ) constraints of the form $p_{i} = j$ ( $0 \leq i, j < N$ ). Count the number of permutations in $S$ satisfying all constraints, modulo $1 0^{9} + 7$ .

The maximum possible value of $f (p)$ is $2$ , and $S = {[2, 0, 3, 1], [1, 3, 0, 2]}$ .

$p = [5, 0, 6, 1, 7, 2, 9, 4, 10, 3, 8]$ should be counted for all test cases.

$p = [4, 9, 3, 8, 2, 7, 0, 5, 10, 1, 6]$ should be counted for all test cases.

Make sure to output the answer modulo $1 0^{9} + 7$ .

SCORING:

Input 5: $N = 15$
Input 6: $N = 2000$
Inputs 7-9: For all test cases, the constraint $p_{0} = ⌊ N /2 ⌋$ appears.
Inputs 10-13: For all test cases, there exists some constraint $p_{i} = j$ with $j$ equal to $⌊ N /2 ⌋$ .
Inputs 14-20: No additional constraints.

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

The first line contains $T$ ( $1 \leq T N \leq 2 \cdot 1 0^{4}$ ) and $N$ , meaning that you will need to solve $T$ independent test cases, each specified by a different set of constraints.

Each test case starts with $K$ , followed by $K$ lines each containing $i$ and $j$ . It is guaranteed that

The same $i$ does not appear more than once within the same test case.
The same $j$ does not appear more than once within the same test case.

Output Format

For each test case, the answer modulo $1 0^{9} + 7$ on a separate line.

Sample Input 1

3 4 0 1 1 1 2 0 2 2 3

Sample Output 1

2 0 1

Sample Input 2

9 11 2 0 5 6 9 3 0 5 6 9 1 0 4 0 5 6 9 1 0 4 7 5 0 5 6 9 1 0 4 7 2 6 6 0 5 6 9 1 0 4 7 2 6 9 3 7 0 5 6 9 1 0 4 7 2 6 9 3 5 2 8 0 5 6 9 1 0 4 7 2 6 9 3 5 2 7 4 9 0 5 6 9 1 0 4 7 2 6 9 3 5 2 7 4 3 1 10 0 5 6 9 1 0 4 7 2 6 9 3 5 2 7 4 3 1 8 10

Sample Output 2

6 6 1 1 1 1 1 1 1

Sample Input 3

10 11 0 1 3 8 2 3 8 5 7 3 3 8 5 7 4 2 4 3 8 5 7 4 2 10 6 5 3 8 5 7 4 2 10 6 8 10 6 3 8 5 7 4 2 10 6 8 10 1 9 7 3 8 5 7 4 2 10 6 8 10 1 9 7 5 8 3 8 5 7 4 2 10 6 8 10 1 9 7 5 2 3 9 3 8 5 7 4 2 10 6 8 10 1 9 7 5 2 3 6 0

Sample Output 3

160 20 8 7 2 1 1 1 1 1

Sample Input 4

5 987 3 654 321 543 210 432 106 2 654 321 543 210 1 654 321 1 0 493 0

Sample Output 4

0 538184948 693625420 932738155 251798971

Submit

Language