| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 2048 MB | 3 | 3 | 3 | 100.000% |
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
For each test case, the answer modulo $10^9+7$ on a separate line.
3 4 0 1 1 1 2 0 2 2 3
2 0 1
The maximum possible value of $f(p)$ is $2$, and $S=\{[2,0,3,1], [1,3,0,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
6 6 1 1 1 1 1 1 1
$p=[5, 0, 6, 1, 7, 2, 9, 4, 10, 3, 8]$ should be counted for all test cases.
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
160 20 8 7 2 1 1 1 1 1
$p=[4, 9, 3, 8, 2, 7, 0, 5, 10, 1, 6]$ should be counted for all test cases.
5 987 3 654 321 543 210 432 106 2 654 321 543 210 1 654 321 1 0 493 0
0 538184948 693625420 932738155 251798971
Make sure to output the answer modulo $10^9+7$.