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

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

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

Енгізу

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

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

• $1\le N\le 2\times {10}^5$

• $1\le A_i,B_i\le {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