Вам дано целое число \(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. Например, последовательности (())(), (), (()(())) и пустая строка являются правильными, а )(, (() и (())( — нет.
Выходные данные
Для каждого набора входных данных выведите количество гиперправильных скобочных последовательностей по модулю \(998\,244\,353\).