PivotOJ

Maximize Minimum Difference

시간 제한: 4000ms메모리 제한: 2048MB출처: USACO 2024 December PlatinumBOJ 33055

문제

Moo! You are given an integer NN (2≤N≤20002\le N\le 2000). Consider all permutations p=[p0,p1,…,pN−1]p=[p_0,p_1,\dots, p_{N-1}] of [0,1,2…,N−1][0,1,2\dots, N-1]. Let f(p)=min⁡i=0N−2∣pi−pi+1∣f(p)=\min_{i=0}^{N-2}|p_i-p_{i+1}| denote the minimum absolute difference between any two consecutive elements of pp. and let SS denote the set of all pp that achieve the maximum possible value of f(p)f(p).

You are additionally given KK (0≤K≤N0\le K\le N) constraints of the form pi=jp_i=j (0≤i,j<N0\le i,j<N). Count the number of permutations in SS satisfying all constraints, modulo 109+710^9+7.

입력

The first line contains TT (1≤TN≤2⋅1041\le TN\le 2\cdot 10^4) and NN, meaning that you will need to solve TT independent test cases, each specified by a different set of constraints.

Each test case starts with KK, followed by KK lines each containing ii and jj. It is guaranteed that

  • The same ii does not appear more than once within the same test case.
  • The same jj does not appear more than once within the same test case.

출력

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

예제

예제 1

입력
3 4
0
1
1 1
2
0 2
2 3
출력
2
0
1

예제 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

예제 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
출력
160
20
8
7
2
1
1
1
1
1

예제 4

입력
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
코드를 제출하려면 로그인하세요.