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