分数: 650 点
问题陈述
Snuke 遇到了以下问题。
给你排列 P=(P_1,P_2,\ldots,P_N) 和 Q=(Q_1,Q_2,\ldots,Q_N) of (1,2,\ldots,N)。 让我们构建一个图表 N 顶点和 N 边缘如下。
- 对于 i=1,2,\ldots,N 按此顺序,绘制权重的边缘 Q_i 连接顶点 i 和 P_i 双向。
当删除一定数量的边以消除图中的环时,找到已删除边的最小可能总权重。
Alice 和 Bob 提出了以下解决方案。
爱丽丝: 初始化答案 0。对于 i=1,2,\ldots,N 按此顺序,如果边连接顶点 i 和 P_i 包含在一个循环中,删除该边并将其权重添加到答案中。
鲍勃: 初始化答案 0。对于 i=N,N-1,\ldots,1 按此顺序,如果边连接顶点 i 和 P_i 包含在一个循环中,删除该边并将其权重添加到答案中。
Snuke 意识到他们的解决方案都是错误的,他想知道他们的解决方案都没有给出正确答案的输入数量。
其中 (N!)^2 可能的输入,找到数字,模数 998244353,Alice 和 Bob 的解决方案均未给出正确答案的输入。
约束
- 1\leq N\leq 2\times 10^5
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
输出
将答案打印为整数。
示例输入 1
3
示例输出 1
4
以下四个输入满足条件。
- P=(2,3,1),Q=(2,1,3)
- P=(2,3,1),Q=(3,1,2)
- P=(3,1,2),Q=(2,1,3)
- P=(3,1,2),Q=(3,1,2)
例如,对于输入 P=(2,3,1),Q=(2,1,3),正确答案是 1,但是爱丽丝的解决方案给出了 2 和鲍勃的给予 3.
示例输入 2
2
示例输出 2
0
可能没有满足条件的输入。
示例输入 3
6
示例输出 3
314708
示例输入 4
318
示例输出 4
321484323