F. Пересечение и объединение
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ отрезков на координатной прямой. $$$i$$$-й отрезок — это $$$[l_i, r_i]$$$. Обозначим множество всех целочисленных точек, принадлежащих $$$i$$$-му отрезку, за $$$S_i$$$.

Пусть $$$A \cup B$$$ — объединение множеств $$$A$$$ и $$$B$$$, $$$A \cap B$$$ — пересечение множеств $$$A$$$ и $$$B$$$, а $$$A \oplus B$$$ — симметрическая разность $$$A$$$ и $$$B$$$ (множество, в которые входят все элементы $$$A$$$ и все элементы $$$B$$$, кроме тех, которые встречаются в обоих множествах).

Пусть $$$[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$$$ — массив, где каждый элемент — либо $$$\cup$$$, либо $$$\oplus$$$, либо $$$\cap$$$. По всем $$$3^{n-1}$$$ способам выбрать этот массив посчитайте сумму следующих значений:

$$$$$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$$$$$

В этом выражении $$$|S|$$$ означает размер множества $$$S$$$.

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

В первой строке задано одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).

Затем следуют $$$n$$$ строк. В $$$i$$$-й из них заданы два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$0 \le l_i \le r_i \le 3 \cdot 10^5$$$).

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

Выведите одно целое число — сумму $$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$$ по всем возможным способам выбрать $$$[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$$$. Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.

Примеры
Входные данные
4
3 5
4 8
2 2
1 9
Выходные данные
162
Входные данные
4
1 9
3 5
4 8
2 2
Выходные данные
102