Вам даны \(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\).
Выходные данные
Выведите одно целое число — сумму \(|(((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\).