005 - Rightarrow

問題

長さ$ \ N \ $の数列$ \ A = (A_1,A_2,\ldots,A_N), B = (B_1, B_2, \ldots, B_N) \ $が与えられます。

ここで、次の条件を満たす集合$ \ S \ $をよい集合であると定義します。

• $S \ $は$ \ \{1,2,\ldots,N\} \ $の部分集合である。
• $S \ $に含まれる任意の整数$ \ i,j \ $について、$A_i \neq A_j \ $ならば$ \ B_i \neq B_j \ $である。

$\{1,2,\ldots,N\} \ $の部分集合として考えられるものは$ \ 2^N \ $通りありますが、その中でよい集合であるものの個数を$ \ 998244353 \ $で割ったあまりを求めてください。

入力

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

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

出力

答えを一行に出力せよ。出力の末尾には改行を入れること。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i,B_i \leq N$
• 入力は全て整数

入出力例

入力例

3
1 2 3
1 2 1

出力例

6

よい集合は$ \ \varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{2,3\} \ $の$ \ 6 \ $つなので$ \ 6 \ $を出力すればよいです。条件を満たさない例として、$ \ \{1,2,3\} \ $は$\ i=1,j=3 \ $について$ \ A_i \neq A_j \ $ですが$ \ B_i = B_j \ $なので条件を満たしません。