페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8190
서브태스크

Maximize Minimum Difference 4초 1024MB

문제

Moo! You are given an integer N (2≤N≤2000). Consider all permutations p=[p_0,p_1,…,p_{N−1}] of [0,1,2…,N−1]. Let f(p)=min^{N−2}_{i=0}|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≤K≤N) constraints of the form p_i=j (0≤i,j<N). Count the number of permutations in S satisfying all constraints, modulo 10^9+7.


입력

The first line contains T (1≤TN≤2⋅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.


부분문제

번호 점수 조건
#110점

N\le15

#220점

N\le2000

#320점

For all test cases, the constraint p_0=⌊N/2⌋ appears.

#420점

For all test cases, there exists some constraint p_i=j with j equal to ⌊N/2⌋.

#530점

No additional constraints.


예제1

입력
34
0
1
11
2
02
23
출력
2
0
1

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


예제2

입력
911
2
05
69
3
05
69
10
4
05
69
10
47
5
05
69
10
47
26
6
05
69
10
47
26
93
7
05
69
10
47
26
93
52
8
05
69
10
47
26
93
52
74
9
05
69
10
47
26
93
52
74
31
10
05
69
10
47
26
93
52
74
31
810
출력
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.


예제3

입력
1011
0
1
38
2
38
57
3
38
57
42
4
38
57
42
106
5
38
57
42
106
810
6
38
57
42
106
810
19
7
38
57
42
106
810
19
75
8
38
57
42
106
810
19
75
23
9
38
57
42
106
810
19
75
23
60
출력
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.


예제4

입력
5987
3
654321
543210
432106
2
654321
543210
1
654321
1
0493
0
출력
0
538184948
693625420
932738155
251798971

Make sure to output the answer modulo 10^9+7.


출처

USACO 2024 December Platinum

역링크