$1$ から $N$ までの各整数がラベル付けされた箱が $1$ つずつあります。また、各整数 $1$ から $N$ について、その整数がラベル付けされたボールが $M$ 個ずつあります。
これらの $NM$ 個のボールはシャッフルされた後、$N$ 個の箱に分配され、各箱にはちょうど $M$ 個のボールが入ります。
ボールを区別する場合、ボールの配置方法は $\frac{(NM)!}{(M!)^N}$ 通りあり、これらの配置はすべて等確率で発生します。
あなたはこれらの箱とボールに対して操作を行います。1 回の操作は以下のステップで構成されます。
- 箱を $1$ つ選び、その箱の前に移動する。
- その箱にボールがない場合、操作を終了する。
- その箱からボールを $1$ つ選び、箱の外に捨てる。
- 最後に、直前に捨てたボールのラベルと同じラベルを持つ箱の前に移動し、ステップ 2 に戻る。
すべての $NM$ 個のボールが捨てられるまでに必要な操作回数をスコアと定義します。あなたはこのスコアを最小化したいと考えています。
最適に行動したときのスコアの期待値を $998244353$ で割った余りを求めてください。
入力
入力は以下の形式で与えられます。
$N$ $M$
ただし、$1 \le N \le 10^5$、$1 \le M \le 100$ を満たします。
出力
答えを出力してください。
入出力例
入力 1
2 2
出力 1
166374060
入力 2
3 1
出力 2
831870296
入力 3
100000 100
出力 3
402978825
注記
最初の例について、ボールの配置とそれに対応する最適な操作方法は以下の通りです。
箱 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$ です。したがって、$166374060$ を出力します。これはこの値を $998244353$ で割った余りです。
期待値の $998244353$ を法とする定義
求める期待値は常に有理数であることが証明できます。また、この問題の制約下では、期待値が既約分数 $\frac{y}{x}$ と書けるとき、$x$ は $998244353$ で割り切れないことが保証されています。
この場合、$0$ 以上 $998244352$ 以下の整数 $z$ で、$xz \equiv y \pmod{998244353}$ を満たすものが一意に存在します。この $z$ を出力してください。