D. Истинные вставки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим алгоритм сортировки вставками целочисленной последовательности $$$[a_1, a_2, \ldots, a_n]$$$ длины $$$n$$$ по неубыванию.

Для каждого $$$i$$$ в порядке от $$$2$$$ до $$$n$$$ делаем следующее. Если $$$a_i \ge a_{i-1}$$$, ничего не делаем и переходим к следующему значению $$$i$$$. В противном случае находим минимальный индекс $$$j$$$ такой, что $$$a_i < a_j$$$, и сдвигаем элементы на позициях с $$$j$$$ по $$$i-1$$$ на одну позицию вправо, а на позицию $$$j$$$ записываем исходное значение $$$a_i$$$. В таком случае мы будем говорить, что произошла вставка элемента с позиции $$$i$$$ на позицию $$$j$$$.

Можно заметить, что после рассмотрения любого $$$i$$$ префикс последовательности $$$[a_1, a_2, \ldots, a_i]$$$ отсортирован по неубыванию, следовательно, алгоритм действительно отсортирует любую последовательность.

Например, сортировка последовательности $$$[4, 5, 3, 1, 3]$$$ происходит так:

  • $$$i = 2$$$: $$$a_2 \ge a_1$$$, ничего не делаем;
  • $$$i = 3$$$: $$$j = 1$$$, вставка с позиции $$$3$$$ на позицию $$$1$$$: $$$[3, 4, 5, 1, 3]$$$;
  • $$$i = 4$$$: $$$j = 1$$$, вставка с позиции $$$4$$$ на позицию $$$1$$$: $$$[1, 3, 4, 5, 3]$$$;
  • $$$i = 5$$$: $$$j = 3$$$, вставка с позиции $$$5$$$ на позицию $$$3$$$: $$$[1, 3, 3, 4, 5]$$$.

Вам дано число $$$n$$$ и список из $$$m$$$ целочисленных пар $$$(x_i, y_i)$$$. Нас интересуют последовательности, при сортировке которых произойдёт ровно $$$m$$$ вставок: сначала элемента с позиции $$$x_1$$$ на позицию $$$y_1$$$, потом элемента с позиции $$$x_2$$$ на позицию $$$y_2$$$, ..., наконец, элемента с позиции $$$x_m$$$ на позицию $$$y_m$$$.

Сколько последовательностей длины $$$n$$$ из (необязательно различных) целых чисел от $$$1$$$ до $$$n$$$ удовлетворяют этому условию? Выведите это число по модулю $$$998\,244\,353$$$.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$0 \le m < n$$$) — длину последовательности и число вставок.

$$$i$$$-я из следующих $$$m$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$2 \le x_1 < x_2 < \ldots < x_m \le n$$$; $$$1 \le y_i < x_i$$$). Эти строки описывают последовательность вставок в хронологическом порядке.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Обратите внимание, что аналогичного ограничения на сумму значений $$$n$$$ нет.

Выходные данные

Для каждого набора входных данных выведите число последовательностей длины $$$n$$$ из целых чисел от $$$1$$$ до $$$n$$$, при сортировке которых алгоритмом из условия будет совершена заданная последовательность вставок, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
3
3 0
3 2
2 1
3 1
5 3
3 1
4 1
5 3
Выходные данные
10
1
21
Примечание

В первом наборе входных данных алгоритм не совершил ни одной вставки — значит, исходная последовательность уже отсортирована по неубыванию. Есть $$$10$$$ таких последовательностей: $$$[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3], [1, 3, 3], [2, 2, 2], [2, 2, 3], [2, 3, 3], [3, 3, 3]$$$.

Во втором наборе входных данных подходит только последовательность $$$[3, 2, 1]$$$.

В третьем наборе входных данных $$$[4, 5, 3, 1, 3]$$$ является одной из подходящих последовательностей.