Lưu ý: Giới hạn thời gian của bài này là 4 giây, gấp đôi mức mặc định.

Moo! Bạn được cho một số nguyên \(N\) (\(2\leq N\leq 2000\)). Xét tất cả các hoán vị \(p=[p_0,p_1,\dots,p_{N-1}]\) của \([0,1,2,\dots,N-1]\). Gọi \(f(p)=\min_{i=0}^{N-2}|p_i-p_{i+1}|\) là hiệu tuyệt đối nhỏ nhất giữa hai phần tử liên tiếp bất kỳ của \(p\), và gọi \(S\) là tập hợp tất cả các hoán vị \(p\) đạt giá trị \(f(p)\) lớn nhất có thể.

Bạn còn được cho \(K\) (\(0\leq K\leq N\)) ràng buộc có dạng \(p_i=j\) (\(0\leq i,j<N\)). Hãy đếm số hoán vị thuộc \(S\) thỏa mãn tất cả các ràng buộc, theo modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu chứa \(T\) và \(N\) (\(1\leq TN\leq 2\cdot 10^4\)), nghĩa là bạn cần giải \(T\) bộ test độc lập, mỗi bộ được xác định bởi một tập ràng buộc khác nhau.

Mỗi bộ test bắt đầu bằng \(K\), tiếp theo là \(K\) dòng, mỗi dòng chứa \(i\) và \(j\). Đảm bảo rằng:

• Cùng một giá trị \(i\) không xuất hiện quá một lần trong cùng một bộ test.
• Cùng một giá trị \(j\) không xuất hiện quá một lần trong cùng một bộ test.

Dữ liệu ra

Với mỗi bộ test, in đáp án theo modulo \(10^9+7\) trên một dòng riêng.

Phân nhóm

• Test 5: \(N=15\).
• Test 6: \(N=2000\).
• Các test 7–9: Trong mọi bộ test đều có ràng buộc \(p_0=\lfloor N/2\rfloor\).
• Các test 10–13: Trong mọi bộ test, tồn tại một ràng buộc \(p_i=j\) với \(j=\lfloor N/2\rfloor\).
• Các test 14–20: Không có ràng buộc bổ sung.

Ví dụ

3 4
0
1
1 1
2
0 2
2 3

2
0
1

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

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

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

Nguồn

Đề bài gốc: USACO 2024 December Contest, Platinum — Maximize Minimum Difference

Tác giả: Benjamin Qi.