[ABC318Ex] Count Strong Test Cases

有这样一个问题：给出一个长为 $n$ 的排列 $p$，并且给出长为 $n$ 的排列 $Q$。依次建立无向边 $(i,P_i,Q_i)$，其中 $Q_i$ 是边权。 现在可以删除一些边，求使得原图不存在环所需删除的边的最小权值和。 Alice 的解决方案是：依次枚举边 $1,2\dots n$，若该边当前情况下在一个环中，将其删掉，并累加答案。 Bob 的解决方案是：依次枚举边 $n,n-1\dots 1$，若该边当前情况下在一个环中，将其删掉，并累加答案。 求对于 $(n!)^2$ 个不同的 $P,Q$ 组合，能使得 Alice 和 Bob 都给出**错误**的答案的排列个数，对 $998244353$ 取模。 $1\le n\le 2\times 10^5$

[problemUrl]: https://atcoder.jp/contests/abc318/tasks/abc318_h すぬけくんは以下の問題を考えました。 > $ (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 の解法がどちらも誤っていることに気付いたので、二人の解法の答えが共に正しい答えと異なるような入力の個数が知りたくなりました。 入力は $ (N!)^2 $ 通り考えられますが、その内 Alice と Bob の解法の答えが共に正しい答えと異なるものの個数を $ 998244353 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $

答えを整数として出力せよ。

3

4

2

0

6

314708

318

321484323

### 制約 - $ 1\leq\ N\leq\ 2\times\ 10^5 $ - 入力される数値は全て整数 ### Sample Explanation 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 $ を答えとします。 ### Sample Explanation 2 条件を満たす入力が存在しない場合もあります。