题目描述

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

考虑翻转 $N$ 张卡片中的任意数量的卡片。给定 $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$

输出

将答案作为一个整数打印出来。

示例输入1

3
1 2
4 2
3 4

示例输出1

4

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

例如，当选择 $S = \{2,3\}$ 时，从卡片 $1$ 到卡片 $3$ 上正面写的整数分别是 $1,2$ 和 $4$，符合条件。

另一方面，当选择 $S = \{3\}$ 时，从卡片 $1$ 到卡片 $3$ 上正面写的整数分别是 $1,4$ 和 $4$，其中卡片 $2$ 和卡片 $3$ 上的整数相同，违反了条件。

满足条件的 $S$ 有 \\{\},\\{1\\},\\{2\\} 和 $\\{2,3\\}$。

示例输入2

4
1 5
2 6
3 7
4 8

示例输出2

16

示例输入3

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

示例输出3

48