9233: ABC291 —— D - Flip Cards
[Creator : ]
Description
### Problem Statement
$N$ cards, numbered $1$ through $N$, are arranged in a line. For each $i\ (1\leq i < N)$, card $i$ and card $(i+1)$ are adjacent to each other. Card $i$ has $A_i$ written on its front, and $B_i$ written on its back. Initially, all cards are face up.
Consider flipping zero or more cards chosen from the $N$ cards. Among the $2^N$ ways to choose the cards to flip, find the number, modulo $998244353$, of such ways that:
- when the chosen cards are flipped, for every pair of adjacent cards, the integers written on their face-up sides are different.
$N$ cards, numbered $1$ through $N$, are arranged in a line. For each $i\ (1\leq i < N)$, card $i$ and card $(i+1)$ are adjacent to each other. Card $i$ has $A_i$ written on its front, and $B_i$ written on its back. Initially, all cards are face up.
Consider flipping zero or more cards chosen from the $N$ cards. Among the $2^N$ ways to choose the cards to flip, find the number, modulo $998244353$, of such ways that:
- when the chosen cards are flipped, for every pair of adjacent cards, the integers written on their face-up sides are different.
Input
### Input
The input is given from Standard Input in the following format:
```
$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$
```
The input is given from Standard Input in the following format:
```
$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$
```
Output
### Output
Print the answer as an integer.
Print the answer as an integer.
Constraints
### Constraints
- $1\leq N \leq 2\times 10^5$
- $1\leq A_i,B_i \leq 10^9$
- All values in the input are integers.
- $1\leq N \leq 2\times 10^5$
- $1\leq A_i,B_i \leq 10^9$
- All values in the input are integers.
Sample 1 Input
3
1 2
4 2
3 4
Sample 1 Output
4
Let S be the set of card numbers to flip.
For example, when S={2,3} is chosen, the integers written on their visible sides are 1,2, and 4, from card 1 to card 3, so it satisfies the condition.
On the other hand, when S={3} is chosen, the integers written on their visible sides are 1,4, and 4, from card 1 to card 3, where the integers on card 2 and card 3 are the same, violating the condition.
Four S satisfy the conditions: {},{1},{2}, and {2,3}.
For example, when S={2,3} is chosen, the integers written on their visible sides are 1,2, and 4, from card 1 to card 3, so it satisfies the condition.
On the other hand, when S={3} is chosen, the integers written on their visible sides are 1,4, and 4, from card 1 to card 3, where the integers on card 2 and card 3 are the same, violating the condition.
Four S satisfy the conditions: {},{1},{2}, and {2,3}.
Sample 2 Input
4
1 5
2 6
3 7
4 8
Sample 2 Output
16
Sample 3 Input
8
877914575 602436426
861648772 623690081
476190629 262703497
971407775 628894325
822804784 450968417
161735902 822804784
161735902 822804784
822804784 161735902
Sample 3 Output
48