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