問題文

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

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

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

制約

• $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$ から順に $1,2,4$ となるため条件を満たします。

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

条件を満たす $S$ は $\\{\\},\\{1\\},\\{2\\},\\{2,3\\}$ の $4$ 通りです。

入力例 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