AT_arc185_d [ARC185D] Random Walk on Tree

[problemUrl]: https://atcoder.jp/contests/arc185/tasks/arc185_d 頂点に $ 0,\ 1,\ \dots,\ N\ \times\ M $ の番号がついた $ N\ \times\ M\ +\ 1 $ 頂点の木があります。$ i $ 本目の辺 $ (1\ \leq\ i\ \leq\ N\ \times\ M) $ は頂点 $ i $ と頂点 $ \max(i\ -\ N,\ 0) $ を結ぶ辺です。 また、頂点 $ 0 $ には色が塗られています。それ以外の頂点は色が塗られていません。 高橋君は頂点 $ 0 $ にいます。高橋君は色が塗られていない頂点が存在する間、次の操作を行います。 - 自身がいる頂点に隣接する頂点の中から一様ランダムに頂点を $ 1 $ つ選んで、その頂点に移動する。(全ての選択は独立である。) そして、今いる頂点に色が塗られていなければ色を塗る。 操作を行う回数の期待値を $ \text{mod\ }998244353 $ で求めてください。 期待値 $ \text{mod\ }{998244353} $ の定義 求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $ \frac{P}{Q} $ で表した時、$ Q\ \not\ \equiv\ 0\ \pmod{998244353} $ となることも証明できます。このとき、$ R\ \times\ Q\ \equiv\ P\ \pmod{998244353},\ 0\ \leq\ R\ \lt\ 998244353 $ を満たす整数 $ R $ が一意に定まります。この $ R $ を答えてください。

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

操作を行う回数の期待値を $ \text{mod\ }998244353 $ で出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ M\ \leq\ 2\ \times\ 10^5 $ - $ N,\ M $ は整数 ### Sample Explanation 1 高橋君は例えば以下のように行動します。 - 頂点 $ 1 $ に移動して、頂点に色を塗る。この行動が選択される確率は $ \frac{1}{2} $ である。 - 頂点 $ 0 $ に移動する。この行動が選択される確率は $ \frac{1}{2} $ である。 - 頂点 $ 1 $ に移動する。この行動が選択される確率は $ \frac{1}{2} $ である。 - 頂点 $ 3 $ に移動して、頂点に色を塗る。この行動が選択される確率は $ \frac{1}{2} $ である。 - 頂点 $ 1 $ に移動する。この行動が選択される確率は $ 1 $ である。 - 頂点 $ 0 $ に移動する。この行動が選択される確率は $ \frac{1}{2} $ である。 - 頂点 $ 2 $ に移動して、頂点に色を塗る。この行動が選択される確率は $ \frac{1}{2} $ である。 - 頂点 $ 4 $ に移動して、頂点に色を塗る。この行動が選択される確率は $ \frac{1}{2} $ である。 高橋君がこのように行動する確率は $ \frac{1}{128} $ で、この時の操作回数は $ 8 $ 回です。また、操作回数の期待値は $ 20 $ 回です。