Contest Duration: - (local time) (100 minutes) Back to Home
F - Cards /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

1,\ldots,N の番号がついた N 枚のカードがあり、カード i の表には P_i が、裏には Q_i が書かれています。
ここで、P=(P_1,\ldots,P_N) 及び Q=(Q_1,\ldots,Q_N) はそれぞれ (1, 2, \dots, N) の並び替えです。

N 枚のカードから何枚かを選ぶ方法のうち、次の条件を満たすものは何通りありますか？　998244353 で割った余りを求めてください。

### 制約

• 1 \leq N \leq 2\times 10^5
• 1 \leq P_i,Q_i \leq N
• P,Q はそれぞれ (1, 2, \dots, N) の並び替えである
• 入力に含まれる値は全て整数である

### 入力

N
P_1 P_2 \ldots P_N
Q_1 Q_2 \ldots Q_N


### 入力例 1

3
1 2 3
2 1 3


### 出力例 1

3


### 入力例 2

5
2 3 5 4 1
4 2 1 3 5


### 出力例 2

12


### 入力例 3

8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8


### 出力例 3

1


Score : 500 points

### Problem Statement

There are N cards numbered 1,\ldots,N. Card i has P_i written on the front and Q_i written on the back.
Here, P=(P_1,\ldots,P_N) and Q=(Q_1,\ldots,Q_N) are permutations of (1, 2, \dots, N).

How many ways are there to choose some of the N cards such that the following condition is satisfied? Find the count modulo 998244353.

Condition: every number 1,2,\ldots,N is written on at least one of the chosen cards.

### Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq P_i,Q_i \leq N
• P and Q are permutations of (1, 2, \dots, N).
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N
Q_1 Q_2 \ldots Q_N


### Output

Print the answer.

### Sample Input 1

3
1 2 3
2 1 3


### Sample Output 1

3


For example, if you choose Cards 1 and 3, then 1 is written on the front of Card 1, 2 on the back of Card 1, and 3 on the front of Card 3, so this combination satisfies the condition.

There are 3 ways to choose cards satisfying the condition: \{1,3\},\{2,3\},\{1,2,3\}.

### Sample Input 2

5
2 3 5 4 1
4 2 1 3 5


### Sample Output 2

12


### Sample Input 3

8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8


### Sample Output 3

1