分数: 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