← 返回题目列表

AtCoder · abc318_h

Ex. 计算强测试用例

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

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