Score : $400$ points

问题描述

设有 $N$ 张卡片，编号从 $1$ 到 $N$，在一条线上排列。对于每个 $i\ (1\leq i < N)$，第 $i$ 张卡片和第 $(i+1)$ 张卡片相邻。第 $i$ 张卡片正面写有数字 $A_i$，背面写有数字 $B_i$。最初，所有卡片都是正面朝上。

考虑从这 $N$ 张卡片中选择零张或多张进行翻转。在 $2^N$ 种选择卡片翻转的方式中，找出满足以下条件的翻牌方式的数量（模 $998244353$）：

• 当所选卡片被翻转后，每对相邻卡片的正面朝上的整数都不相同。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

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.

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$

Output

Print the answer as an integer.

Sample Input 1

3
1 2
4 2
3 4

Sample Output 1

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\}$.

Sample Input 2

4
1 5
2 6
3 7
4 8

Sample Output 2

16

Sample Input 3

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

Sample Output 3

48

update @ 2024/3/10 12:08:51