**Замечание: Время на тест в этой задаче 4 сек,
в два раза больше, чем по умолчанию.**
Вам дано целое число \(N\) (\(2\le N\le 2000\)).
Рассмотрим все перестановки
\([p_0,p_1,\dots, p_{N-1}]\) из \([0,1,2\dots, N-1]\).
Пусть \(f(p)=\min_{i=0}^{N-2}|p_i-p_{i+1}|\) означает
минимальную абсолютную разность между двумя последовательными элементами
в \(p\). Также обозначим \(S_N\) множество всех таких перестановок \(p\),
которые достигают максимальной возможной величины \(f(p)\).
Также Вам дополнительно дано \(K\) (\(0\le K\le N\)) ограничений вида
\(p_i=j\) (\(0\le i,j<N\)). Посчитайте количество перестановок в \(S_N\),
удовлетворяющих всем ограничениям, по модулю \(10^9+7\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(T\) (
\(1\le TN\le 2\cdot 10^4\)) и
\(N\),
означающие, что Вы должны решить
\(T\) независимых подтестов,
в каждом из которых указано различное множество ограничений.
Каждый подтест начинается с \(K\), за которым следуют \(K\) строк
каждая из них содержит \(i\) \(j\).
Гарантируется, что
- \(i\) появится не более одного раза внутри одного подтеста.
- \(j\) появится не более одного раза внутри одного подтеста.
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста выведите ответ по модулю \(10^9+7\) на отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
0
1
1 1
2
0 2
2 3
|
2
0
1
|