005 - Rightarrow

時間制限 2 秒 / メモリ制限 1024 MB / 得点 400 / x 1 /


TLE
2sec
MLE
1024MB
得点
400

問題

長さ$ \ 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 \ $で割ったあまりを求めてください。

  • よい集合のより形式的な定義
    • $S \subseteq \{1,2,\ldots,N\}$
    • $\forall i,j \in S, A_i \neq A_j \Rightarrow B_i \neq B_j \ $

    入力

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

    $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 \ $なので条件を満たしません。