この問題は、形式的冪級数（以下 FPS）の \(\exp\) の練習問題となっています。

FPS \(f\) に対して、 \(\exp(f)\) は \([x^0]f=0\) を満たすときに以下で定義されます。

• \(\displaystyle \exp(f) = \sum_{n=0}^\infty \frac{f^n}{n!}\)

\(\exp(f)\) の先頭 \(N\) 項は、FPS の逆元をニュートン法を用いて求める手法（参考：ABC 260-Ex 解説）と同様に、ニュートン法を用いて \(\mathrm{O}(N\log N)\) で求めることができます。参考：Nyaan’s Library）

それでは本問題の解説に移ります。

---

この問題の答えは、（テストケースの総数）\(-\) （Alice が AC、Bob が WA となるテストケースの総数） \(-\) （Bob が AC、Alice が WA となるテストケースの総数） \(-\) （Alice も Bob もAC となるテストケースの総数）

と求まります。対称性より（Alice が AC、Bob が WA となるテストケースの総数） \(=\) （Bob が AC、Alice が WA となるテストケースの総数）が 成立するので、（Alice が AC、Bob が WA となるテストケースの総数）と（Alice も Bob もAC となるテストケースの総数）が求まればよいです。

作られるグラフは、何個かのサイクルに分解できることが分かります。サイクル同士は独立なので、各サイクルについて Alice と Bob の解法が正しい答えを出すか調べます。

サイクルは \(4\) 個のタイプに分類されます。

• Alice も Bob も 正しい答えを出す
• Alice のみ正しい答えを出す
• Bob のみ正しい答えを出す
• Alice も Bob も間違った答えを出す

求めたいものは、Alice も Bob も 正しい答えを出すサイクル \(0\) 個以上と、Alice のみ正しい答えを出すサイクル \(1\) 個以上からなる入力の個数です。

Alice も Bob も正しい答えを出すサイクルは、頂点数 \(1\) のサイクルのみが該当します。

また、Alice のみ正しい答えを出すサイクルは、頂点数 \(2\) 以上のサイクルであって、サイクルに含まれる頂点番号が最小の頂点から張った辺の重みがサイクル内部で最大になっているもののみが該当します。

ここまでの考察から、数え上げを行います。

まず、Alice も Bob も 正しい答えを出すサイクル \(0\) 個以上と、Alice のみ正しい答えを出すサイクル \(\bm{0}\) 個以上からなる入力の個数を求めます。

入力に含まれるサイズ \(i\) のサイクルの個数を \(C_i\) 個と決め打ったとき、答えは以下のように書けます。

\[(N!\prod_{i=1}^N \frac{1}{i!^{C_i}}) (\frac{1}{\prod_{i=1}^N C_i!}) (\prod_{i=1}^N (i-1)!^{C_i})(N!\prod_{i=1}^N(\frac{1}{i})^{C_i}) \]

上式を説明します。

まず、\((N!\prod_{i=1}^N \frac{1}{i!^{C_i}})\) は頂点番号を各サイクルに割り当てる方法、つまり多項係数を表しています。

次に、\( \frac{1}{\prod_{i=1}^N C_i!}\) はサイクルの並べ方に \(\prod_{i=1}^N C_i!\) の任意性があるための項です。

\(\prod_{i=1}^N (i-1)!^{C_i}\) は、サイクル内部の頂点の並べ方を表しています。長さ \(c\) の有向サイクルの個数は、最小の頂点を固定すると長さ \(c-1\) の順列の個数と一致することが分かります。

\(N!\prod_{i=1}^N(\frac{1}{i})^{C_i}\) は辺の重みの割り当て方を表しています。辺の入力は \(N!\) 通りありますが、長さ \(c\) のサイクルについては、そのうち \(\frac{1}{c}\) 倍の入力が、Alice が AC するという条件を満たします。

上の式を全ての \(C\) について和を取るには、FPS を用います。上の式を整理すると以下になります。

\[N!^2 \frac{1}{\prod_{i=1}^N C_i!}\prod_{i=1}^N (\frac{1}{i^{2}})^{C_i}\]

\(f(x) = \sum_{i=1}^N \frac{1}{i^2}x^i\) と置くと、求めたいものは \(N!^2[x^N]1 + f(x) + \frac{f(x)^2}{2!} + \frac{f(x)^3}{3!} + \ldots\) であり、これは \(N!^2 [x^N]\exp(f(x))\) と一致しています。

正確には求めたいものは Alice のみが AC するサイクルが \(1\) 個以上含まれるものでした。しかし、Alice のみが AC するサイクルが \(0\) 個で、全てのサイクルがAlice も Bob も 正しい答えを出すサイクルであるものの個数は \(N!\) と簡単にわかるので問題ありません。

まとめ

\(f(x) = \sum_{i=1}^N \frac{1}{i^2}x^i\) とします。

テストケースの総数： \(N!^2\) 通り

Alice が AC、Bob が WA となるテストケースの総数： \((N!^2 [x^N]\exp(f(x))) - N!\)

Alice が WA、Bob が AC となるテストケースの総数： \((N!^2 [x^N]\exp(f(x))) - N!\)

Alice も Bob も AC となるテストケースの総数： \(N!\)

とわかるので、答えは \(N!^2 (1 - 2 [x^N]\exp(f(x)) )) +N!\) です。