当前没有测试数据。

D - 翻转卡片

得分：400

问题描述

有 $N$ 张卡片，编号为 $1$ 到 $N$，排成一行。对于每个 $i\ (1\leq i < N)$，卡片 $i$ 和卡片 $(i+1)$ 是相邻的。 卡片 $i$ 的正面写着 $A_i$，背面写着 $B_i$。最开始，所有卡片都是正面朝上的。

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

• 当翻转了选定的卡片后，对于每对相邻的卡片，它们正面的数字是不同的。

约束

• $1\leq N \leq 2\times 10^5$
• $1\leq A_i,B_i \leq 10^9$
• 输入中的所有数值都是整数。

输入

输入用以下格式从标准输入给出：

$N$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

输出

将答案作为整数输出。

3
1 2
4 2
3 4

4

设 $S$ 是要翻转的卡片编号的集合。

例如，当选择 $S=\{2,3\}$ 时，从卡片 $1$ 到卡片 $3$，它们正面的数字是 $1,2$ 和 $4$，满足条件。

另一方面，当选择 $S=\{3\}$ 时，从卡片 $1$ 到卡片 $3$，它们正面的数字是 $1,4$ 和 $4$，卡片 $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