← 返回题目列表

AtCoder · abc291_d

G. 翻页卡

中文机器翻译题面 查看原题

分数: 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

输出

将答案打印为整数。


示例输入 1

3
1 2
4 2
3 4

示例输出 1

4

让 S 是要翻转的一组卡号。 选择

例如,当 S=\{2,3\} ,写在其可见侧面的整数是 1,2,和 4,来自卡 1 到卡 3,因此满足条件。

另一方面,当 S=\{3\} ,写在其可见侧面的整数是 1,4,和 4,来自卡 1 到卡 3,其中卡上的整数 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