Maximize Minimum Difference

Moo! You are given an integer $N$ ($2\le N\le 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\le K\le N$) constraints of the form $p_i=j$ ($0\le i,j<N$). Count the number of permutations in $S$ satisfying all constraints, modulo $10^9+7$.

The first line contains $T$ ($1\le TN\le 2\cdot 10^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.

For each test case, the answer modulo $10^9+7$ on a separate line.