/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
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,2,\ldots,N のどの数も選んだカードのいずれかに書かれている
制約
- 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
例えばカード 1,3 を選ぶと、1 はカード 1 の表に、2 はカード 1 の裏に、3 はカード 3 の表に書かれているため条件を満たします。
条件を満たすカードの選び方は \{1,3\},\{2,3\},\{1,2,3\} の 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