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 翻译