102475: [AtCoder]ABC247 F - Cards

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

问题描述

有N张卡片，编号为1，…，N。第i张卡片的正面写着P_i，背面写着Q_i。

其中，P=(P_1, …, P_N)和Q=(Q_1, …, Q_N)是(1, 2, …, N)的一个排列。

满足以下条件的N张卡片的选择方式有多少种？请计算答案对998244353取模。

条件：每一个数1，2，…，N都至少写在所选卡片中的一张上。

约束条件

• 1≤N≤2×10^5
• 1≤P_i，Q_i≤N
• P和Q是(1, 2, …, 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的正面，因此这种组合满足条件。

有3种选择卡片满足条件的方式：$\{1,3\}$，$\{2,3\}$，$\{1,2,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