Maximize Minimum Difference

시간 제한4초메모리 제한2048 MB

요약
각 제약 집합마다 인접한 원소 차이의 최솟값을 최대로 만드는 순열 중 주어진 고정 위치를 만족하는 개수를 10^9+7로 나눈 나머지로 센다.
난이도

어려움10점 중 8점

유형
조합론, 동적 계획법, 수학
정답자
아직 제출이 없습니다

문제

Moo! You are given an integer NN (2≤N≤20002\le N\le 2000). Consider all permutations p=\[p_0,p_1,…,p_N−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∣p_i−p_i+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 p_i=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.

예제4

  1. 예제 1

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

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