E. Вложенные отрезки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Множество $$$A$$$, состоящее из попарно различных отрезков $$$[l, r]$$$ с целочисленными концами, называется хорошим, если $$$1\le l\le r\le n$$$, и для любой пары различных отрезков $$$[l_i, r_i], [l_j, r_j]$$$ из $$$A$$$ выполняется ровно одно из следующих условий:

  • $$$r_i < l_j$$$ или $$$r_j < l_i$$$ (отрезки не пересекаются)
  • $$$l_i \le l_j \le r_j \le r_i$$$ или $$$l_j \le l_i \le r_i \le r_j$$$ (один отрезок полностью содержится внутри другого)

Вам дано хорошее множество $$$S$$$, состоящее из $$$m$$$ попарно различных отрезков $$$[l_i, r_i]$$$ с целочисленными концами. Вы хотите добавить как можно больше дополнительных отрезков к набору $$$S$$$, так, чтобы набор $$$S$$$ остался хорошим.

Поскольку эта задача слишком проста, вам нужно определить количество различных способов добавления максимального числа дополнительных отрезков к $$$S$$$, так, чтобы набор остался хорошим. Два способа считаются разными, если существует отрезок, который добавляется одним из способов, но не другим.

Формально, вам нужно найти количество хороших наборов различных отрезков $$$T$$$, таких, чтобы $$$S$$$ было подмножеством $$$T$$$, и $$$T$$$ имело максимально возможный размер. Поскольку ответ может быть очень большим, вычислите его по модулю $$$998\,244\,353$$$.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) — максимальный правый конец отрезка и размер $$$S$$$.

$$$i$$$-я из следующих $$$m$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — границы отрезков в наборе $$$S$$$

Гарантируется, что данное множество $$$S$$$ является хорошим, и отрезки в множестве $$$S$$$ попарно различны.

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

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

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

Пример
Входные данные
6
1 0
2 3
1 1
2 2
1 2
5 2
1 3
2 3
4 1
1 1
6 2
1 3
4 6
2300 0
Выходные данные
1
1
2
5
4
187997613
Примечание

В первом наборе входных данных единственным возможным отрезком является $$$[1, 1]$$$, поэтому $$$T = \{[1, 1]\}$$$ имеет максимальный размер, и это единственное решение.

Во втором наборе входных данных невозможно добавить какие-либо дополнительные отрезки к набору $$$S$$$. Следовательно, единственный способ добавить отрезки к $$$S$$$ — это ничего не добавлять.

В третьем наборе входных данных можно добавить $$$7$$$ дополнительных отрезков к $$$S$$$, гарантируя, что набор останется хорошим. Можно доказать, что добавление более $$$7$$$ дополнительных отрезков к $$$S$$$ невозможно. Существует ровно $$$2$$$ различных способа добавить эти $$$7$$$ отрезков к $$$S$$$, и соответствующие наборы $$$T$$$ показаны ниже:

  • $$$\{[1, 1], [1, 3], [1, 4], [1, 5], [2, 2], [2, 3], [3, 3], [4, 4], [5, 5]\}$$$
  • $$$\{[1, 1], [1, 3], [1, 5], [2, 2], [2, 3], [3, 3], [4, 4], [4, 5], [5, 5]\}$$$.

В четвертом наборе входных данных существует ровно $$$5$$$ различных способов добавить максимум $$$6$$$ дополнительных отрезков к $$$S$$$, соответствующие наборы $$$T$$$ показаны ниже:

  • $$$\{[1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [3, 3], [4, 4]\}$$$
  • $$$\{[1, 1], [1, 2], [1, 4], [2, 2], [3, 3], [3, 4], [4, 4]\}$$$
  • $$$\{[1, 1], [1, 3], [1, 4], [2, 2], [2, 3], [3, 3], [4, 4]\}$$$
  • $$$\{[1, 1], [1, 4], [2, 2], [2, 3], [2, 4], [3, 3], [4, 4]\}$$$
  • $$$\{[1, 1], [1, 4], [2, 2], [2, 4], [3, 3], [3, 4], [4, 4]\}$$$