\(N\) карта \(1\)-ден \(N\)-ге дейін нөмірленіп, бір қатарға орналастырылған. Әрбір \(i\) үшін (\(1 \leq i < N\)), \(i\)-ші карта мен \((i + 1)\)-ші карта бір-біріне жақын орналасқан. \(i\)-ші картаның бет жағында \(A_i\), ал артқы жағында \(B_i\) жазылған. Алғашында барлық карталар бет жағымен жоғары қарап жатыр.

\(N\) картаның ішінен \(0\) немесе одан көп картаны аударуды қарастырыңыз. Карталарды аударудың \(2^N\) әдісінің ішінде келесі шартты қанағаттандыратын әдістердің санын табыңыз, нәтижені \(998244353\) модулі бойынша есептеңіз:

• Таңдалған карталар аударылған кезде, барлық көрші карталардың бет жағындағы сандары әртүрлі болуы керек.

Енгізу

• Бірінші жолда бүтін сан \(N\).

• Келесі \(N\) жолдың әрқайсысында екі бүтін сан \(A_i\) және \(B_i\) беріледі.

• \(1 \leq N \leq 2 \times 10^5\)

• \(1 \leq A_i, B_i \leq 10^9\)

• Кіріс деректерінің барлық мәндері бүтін сандар.

Шығару

Нәтижені бүтін сан ретінде басып шығарыңыз.

Бағалау жүйесі

• Барлығы 50 тест бар, олардың әрқайсысы 2 ұпайдан тұрады.

• Мысалдар бағаланбайды.

Мысалдар

Енгізу 1

3
1 2
4 2
3 4

Жауап 1

4

Енгізу 2

4
1 5
2 6
3 7
4 8

Жауап 2

16