题目描述

$1$ から $N$ までの番号がついた $N$ 枚のカードが一列に並んでいて、各 $i\ (1\leq\ i\ <\ N)$ に対してカード $i$ とカード $i+1$ が隣り合っています。 カード $i$ の表には $A_i$ が、裏には $B_i$ が書かれており、最初全てのカードは表を向いています。

今から、$N$ 枚のカードのうち好きな枚数 ($0$ 枚でも良い) を選んで裏返すことを考えます。 裏返すカードの選び方は $2^N$ 通りありますが、そのうち以下の条件を満たすものの数を $998244353$ で割った余りを求めてください。

• 選んだカードを裏返した後、どの隣り合う $2$ 枚のカードについても、向いている面に書かれた数が相異なる。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

答えを整数として出力せよ。

题目大意

• 有 $n$ 个卡片排成一排，编号为 $1,2,...,n$。
• 第 $i$ 个卡片的正面是 $a_i$，反面是 $b_i$。
• 现在你可以将每个卡片翻到正面或反面，使相邻两个卡片上的数字互不相同。
• 求方案数对 $998244353$ 取模。
• $1\le n\le2\times10^5$，$1\le a_i,b_i\le 10^9$

3
1 2
4 2
3 4

4

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$
• 入力は全て整数

Sample Explanation 1

裏返すカードの番号の集合を $S$ とします。 例えば $S=\{2,3\}$ を選ぶと、向いている面に書かれた数はカード $1$ から順に $1,2,4$ となるため条件を満たします。 一方 $S=\{3\}$ を選ぶと、向いている面に書かれた数はカード $1$ から順に $1,4,4$ となり、カード $2$ とカード $3$ の数が一致するため条件を満たしません。 条件を満たす $S$ は $\{\},\{1\},\{2\},\{2,3\}$ の $4$ 通りです。