C. Гиперправильные скобочные последовательности
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано целое число $$$n$$$ и $$$k$$$ отрезков. $$$i$$$-й отрезок имеет вид $$$[l_i,r_i]$$$, где $$$1 \leq l_i \leq r_i \leq n$$$.

Правильная скобочная последовательность$$$^{\dagger,\ddagger}$$$ длины $$$n$$$ называется гиперправильной, если для каждого $$$i$$$ такого, что $$$1 \leq i \leq k$$$, подстрока $$$\overline{s_{l_i} s_{l_{i}+1} \ldots s_{r_i}}$$$ также является правильной скобочной последовательностью.

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

$$$^\dagger$$$ Скобочная последовательность — это строка, содержащая только символы «(» и «)».

$$$^\ddagger$$$ Последовательность скобок называется правильной, если её можно превратить в правильное математическое выражение путём добавления символов + и 1. Например, последовательности (())(), (), (()(())) и пустая строка являются правильными, а )(, (() и (())( — нет.

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

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

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

Следующие $$$k$$$ строк каждого набора содержат два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l \le r \le n$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$3 \cdot 10^5$$$, и сумма $$$k$$$ по всем наборам не превышает $$$3 \cdot 10^5$$$.

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

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

Пример
Входные данные
7
6 0
5 0
8 1
1 3
10 2
3 4
6 9
1000 3
100 701
200 801
300 901
28 5
1 12
3 20
11 14
4 9
18 19
4 3
1 4
1 4
1 4
Выходные данные
5
0
0
4
839415253
140
2
Примечание
  • Для первого набора есть $$$5$$$ гиперправильных скобочных последовательностей длины $$$6$$$: ((())), (()()), (())(), ()(()) и ()()().
  • Для второго набора нет правильных скобочных последовательностей длины $$$5$$$, а следовательно, нет гиперправильных скобочных последовательностей длины $$$5$$$.
  • Для третьего набора нет гиперправильных скобочных последовательностей длины $$$8$$$, для которых подстрока $$$[1 \ldots 3]$$$ является правильной скобочной последовательностью.
  • Для четвертого набора существует $$$4$$$ гиперправильные скобочные последовательности: ((())(())), ((())()()), ()()((())) и ()()(()()).