← 返回题目列表

AtCoder · abc247_f

I. 卡

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 卡片编号 1,\ldots,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,所以这个组合满足条件。

有 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