翻牌

题目描述

编号为 $1$ 到 $N$ 的 $N$ 张卡片排成一行。对于每个 $i\ (1\leq i \lt N)$,卡片 $i$ 与卡片 $(i+1)$ 相邻。 卡片 $i$ 的正面写着 $A_i$,背面写着 $B_i$。初始时,所有卡片正面朝上。

考虑从这 $N$ 张卡片中任意选择若干张(可以为 0 张)进行翻转。 在所有 $2^N$ 种选择方式中,求满足以下条件的选择方式的数量,对 $998244353$ 取模:

所选卡片翻转后,对于每一对相邻卡片,它们朝上的一面写着的整数互不相同。

输入格式

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

$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

数据范围

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