Рассмотрим алгоритм сортировки вставками целочисленной последовательности \([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\).
Выходные данные
Для каждого набора входных данных выведите число последовательностей длины \(n\) из целых чисел от \(1\) до \(n\), при сортировке которых алгоритмом из условия будет совершена заданная последовательность вставок, по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных алгоритм не совершил ни одной вставки — значит, исходная последовательность уже отсортирована по неубыванию. Есть \(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]\) является одной из подходящих последовательностей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 0
3 2
2 1
3 1
5 3
3 1
4 1
5 3
|
10
1
21
|