AT_abc318_h.[ABC318Ex] Count Strong Test Cases

すぬけ君想出了如下的问题。

给定 $ (1,2,\ldots,N) $ 的排列 $ P=(P_1,P_2,\ldots,P_N), Q=(Q_1,Q_2,\ldots,Q_N) $。按照以下方法构建一个有 $ N $ 个顶点和 $ N $ 条边的图。

• 对于 $ i=1,2,\ldots,N $，依次将顶点 $ i $ 与顶点 $ P_i $ 之间连接一条权值为 $ Q_i $ 的无向边。

当你删除若干条边使得图中不包含环时，请求出被删除的边的权值之和的最小值。

Alice 和 Bob 分别想出了如下的解法。

Alice：将答案初始化为 $ 0 $。对于 $ i=1,2,\ldots,N $，如果顶点 $ i $ 与顶点 $ P_i $ 之间的边在环中，则删除这条边，并将其权值加到答案中。

Bob：将答案初始化为 $ 0 $。对于 $ i=N,N-1,\ldots,1 $，如果顶点 $ i $ 与顶点 $ P_i $ 之间的边在环中，则删除这条边，并将其权值加到答案中。

すぬけ君发现 Alice 和 Bob 的解法都是错误的，所以他想知道，有多少组输入使得 Alice 和 Bob 的解法的答案都与正确答案不同。

输入共有 $ (N!)^2 $ 种可能，请你输出其中 Alice 和 Bob 的解法的答案都与正确答案不同的输入的个数，模 $ 998244353 $。

输入通过标准输入给出，格式如下：

$ N $

请输出一个整数，表示答案。

限制条件

• $ 1\leq N\leq 2\times 10^5 $
• 输入的所有数均为整数

样例解释 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 $，但 Alice 的解法输出 $ 2 $，Bob 的解法输出 $ 3 $。

样例解释 2

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

由 ChatGPT 4.1 翻译