\(N\) карток, пронумерованих від 1 до \(N\), розташовані в лінію. Для кожного \(i\) (\(1≤i<N\)) картка \(i\) та картка \((i+1)\) суміжні одна з одною. Картка \(i\) містить \(A_i\) ​ на лицьовій стороні та \(B_i\) ​ на звороті.

Спочатку всі карти розгорнуті. Подумайте про те, щоб перевернути нуль або більше карт, вибраних із \(N\) карт. Серед \(2^N\) способів вибору карток, які потрібно перевернути, знайдіть число за модулем 998244353 таких способів, що:

• коли вибрані картки перевертаються, для кожної пари сусідніх карток цілі числа, написані на їхніх лицьових сторонах, відрізняються.

Обмеження

• \(1≤N≤2×10^5\)
• \(1≤A_i ​,B_i ≤10^9\)
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Перший рядок містить ціле число \(N\).

Наступні  \(N\) рядків містять цілі числа \(A_i, B_i\).

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

3
1 2
4 2
3 4

Приклад вихідних даних

4

Нехай \(S\) — набір номерів карток, які потрібно підкинути.

Наприклад, якщо вибрано \(S\)={2,3}, цілі числа, написані на їхніх видимих сторонах, дорівнюють 1,2 і 4, від картки 1 до картки 3, тому умова задовольняє.

З іншого боку, коли вибрано \(S\)={3}, цілі числа, написані на їхніх видимих сторонах, є 1, 4 і 4, від картки 1 до картки 3, де цілі числа на картці 2 і картці 3 однакові, порушуючи стан.

Чотири \(S\) задовольняють умови: {}, {1}, {2} і {2,3}.

Приклад вхідних даних

4
1 5
2 6
3 7
4 8

Приклад вихідних даних

16

Приклад вхідних даних

8
877914575 602436426
861648772 623690081
476190629 262703497
971407775 628894325
822804784 450968417
161735902 822804784
161735902 822804784
822804784 161735902

Приклад вихідних даних

48