Statement
\(1\) から \(N\) の番号が付けられた箱が一つずつあります。また、 \(1\) から \(N\) の番号がつけられたボールがそれぞれ \(M\) 個ずつあります。
これら \(NM\) 個のボールをシャッフルし、先に書いた \(N\) 個の箱にそれぞれ \(M\) 個ずつ入れます。
考えられるボールの入れ方は (すべてのボールを区別できるものとすると) \(\frac{(NM)!}{(M!)^N}\) 通りありますが、これらは等確率で現れます。
あなたはこれらの箱とボールに操作をします。\(1\) 回の操作は以下の手順からなります。
- 箱をひとつ選び、その箱の前に行く
- その箱にボールが入っていなければ、操作を終了する。
- その箱の中からボールを任意に \(1\) つ選び、箱の外に捨てる。
- 最後に捨てたボールの番号と一致する番号の箱の前に行き、 2. に戻る
\(NM\) 個全てのボールが捨てられるまでに要した操作回数をあなたの 点数 とします。あなたはこの点数を 最小化 したいです。
最適に行動した場合の点数の 期待値 を \(\bmod{998244353}\) で求めてください。
Note
\(1\) つ目のサンプルについて、ボールの入れ方とそれに対応する最適な操作の方法は以下のようになります。
- 箱 \(1\) に \(1\) が付いたボールを \(2\) 個、箱 \(2\) に \(2\) が付いたボールを \(2\) 個入れる。 ( 確率 \(1/6\) )
- \(1\) 度目の操作で、箱 \(1\) の前に行く。そこから \(1\) が付いたボールを取り出し、箱 \(1\) の前に行く。そこからもう一度 \(1\) が付いたボールを取り出し、箱 \(1\) の前に行く。この時点で箱 \(1\) は空なので、操作を終了する。
- \(2\) 度目の操作で、箱 \(2\) の前に行く。そこから \(2\) が付いたボールを取り出し、箱 \(2\) の前に行く。そこからもう一度 \(2\) が付いたボールを取り出し、箱 \(2\) の前に行く。この時点で箱 \(2\) は空なので、操作を終了する。
- この場合、達成可能な点数の最小値は \(2\) です。
- 箱 \(1\) にも箱 \(2\) にも \(1\) が付いたボールを \(1\) 個と \(2\) が付いたボールを \(1\) 個入れる。 ( 確率 \(2/3\) )
- \(1\) 度目の操作で、箱 \(1\) の前に行く。そこから \(1\) が付いたボールを取り出し、箱 \(1\) の前に行く。そこから \(2\) が付いたボールを取り出し、箱 \(2\) の前に行く。そこから \(2\) が付いたボールを取り出し、箱 \(2\) の前に行く。そこから \(1\) が付いたボールを取り出し、箱 \(1\) の前に行く。この時点で箱 \(1\) は空なので、操作を終了する。
- この場合、達成可能な点数の最小値は \(1\) です。
- 箱 \(1\) に \(2\) が付いたボールを \(2\) 個、箱 \(2\) に \(1\) が付いたボールを \(2\) 個入れる。 ( 確率 \(1/6\) )
- \(1\) 度目の操作で、箱 \(1\) の前に行く。そこから \(2\) が付いたボールを取り出し、箱 \(2\) の前に行く。そこから \(1\) が付いたボールを取り出し、箱 \(1\) の前に行く。そこから \(2\) が付いたボールを取り出し、箱 \(2\) の前に行く。そこから \(1\) が付いたボールを取り出し、箱 \(1\) の前に行く。この時点で箱 \(1\) は空なので、操作を終了する。
- この場合、達成可能な点数の最小値は \(1\) です。
まとめると、確率 \(1/6\) でスコアの最小値が \(2\) 、確率 \(5/6\) でスコアの最小値が \(1\) となり、全体でスコアの期待値は \(7/6\) となります。 これを \(\bmod{998244353}\) 上で表現した \(166374060\) を出力してください。
期待値 \(\bmod{998244353}\) の定義について 求める期待値は必ず有理数になることが証明できます。また、この問題の制約下では、求める期待値を既約分数 \(\frac{y}{x}\) で表したとき、\(x\) が \(998244353\) で割り切れないことが保証されます。
このとき、\(xz \equiv y \pmod{998244353}\) を満たす \(0\) 以上 \(998244352\) 以下の整数 \(z\) が一意に定まります。この \(z\) を答えてください。