统计强测试用例

题目描述

Snuke 想出了下面这个问题。

给定 $(1,2,\dots,N)$ 的两个排列 $P=(P_1,P_2,\dots,P_N)$ 和 $Q=(Q_1,Q_2,\dots,Q_N)$。

按照以下方式构造一个具有 $N$ 个顶点和 $N$ 条边的图。

对于 $i=1,2,\dots,N$,按顺序画一条连接顶点 $i$ 和顶点 $P_i$ 的无向边,权值为 $Q_i$。

当移除若干条边以消除图中的环时,求被移除边的权值总和的最小值。

Alice 和 Bob 想出了以下解法。

Alice:将答案初始化为 $0$。对于 $i=1,2,\dots,N$,按顺序执行:如果连接顶点 $i$ 和顶点 $P_i$ 的边包含在某个环中,则移除该边并将其权值加到答案上。

Bob:将答案初始化为 $0$。对于 $i=N,N-1,\dots,1$,按顺序执行:如果连接顶点 $i$ 和顶点 $P_i$ 的边包含在某个环中,则移除该边并将其权值加到答案上。

Snuke 发现他们的解法都不正确,他想知道有多少组输入使得他们两人的解法都无法给出正确答案。

在所有 $(N!)^2$ 组可能的输入中,求使得 Alice 和 Bob 的解法都无法给出正确答案的输入组数,对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入给出。

$N$

输出格式

以整数形式输出答案。

样例

3

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$,但 Alice 的解法给出 $2$,Bob 的解法给出 $3$。

2

0

也可能不存在满足条件的输入。

6

314708

318

321484323

数据范围

• $1 \le N \le 2 \times 10^5$
• 所有输入值均为整数。