Множество \(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\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество различных способов, которыми вы можете добавить максимальное количество дополнительных отрезков к набору \(S\), гарантируя при этом, что набор \(S\) останется хорошим, по модулю \(998\,244\,353\)
Примечание
В первом наборе входных данных единственным возможным отрезком является \([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]\}\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|