AT_nupc2024_i Eat and Build

ビーバーのメイダイ君は、木を使って $ K $ 個の家を作ろうと思っています。 メイダイ君は、次のどちらかの行動を取ります。 - 行動 $ 1 $ : 木を $ 1 $ 本使って家を $ 1 $ 個作る。メイダイ君の体力は $ 1 $ 減る。 - 行動 $ 2 $ : 木を $ 1 $ 本食べる。メイダイ君の体力は $ 1 $ 増える。 最初、メイダイ君の体力は $ H $ です。 メイダイ君は体力が $ h $ のとき、 $ \frac{h}{H} $ の確率で行動 $ 1 $ を、 $ \frac{H-h}{H} $ の確率で行動 $ 2 $ をします。 メイダイ君は、家を $ K $ 個作った時点で行動を終了します。また、木は無限に存在するとして、家を $ K $ 個作るまで行動を終了することはありません。 $ K $ 個の家を作るまでに 行動 $ 1 $ と行動 $ 2 $ で消費される合計の木の本数の期待値を有理数 $ \bmod~998244353 $ で求めてください。 ただし、行動 $ 1 $ と 行動 $ 2 $ で、木はちょうど $ 1 $ 本ずつ消費され、これらの行動以外で木を消費したり、体力が増えたり減ったりすることはありません。 有理数 $ \bmod~998244353 $ とは 求める期待値は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な $ 2 $ つの整数 $ P,Q $ を用いて $ P / Q $ と表したとき、 $ R \times Q \equiv P \pmod{998244353} $ かつ $ 0 \leq R < 998244353 $ を満たすを満たす整数 $ R $ がただ一つ存在することが証明できます。 この $ R $ を求めてください。

入力は以下の形式で標準入力から与えられます。 > $ H $ $ K $

答えを出力せよ。

### Sample Explanation 1 最初、メイダイ君の体力は $ 2 $ です。このとき、確率 $ \frac{2}{2} = 1 $ で家を作ります。すると、メイダイ君の体力は $ 1 $ になります。次に、メイダイ君は以下の $ 2 $ 通りの行動を取ります。 1. $ \frac{1}{2} $ の確率で行動 $ 1 $ を取る。 $ 2 $ 個目の家を作り、メイダイ君の体力は $ 0 $ になります。 2. $ \frac{2-1}{2} = \frac{1}{2} $ の確率で行動 $ 2 $ を取る。家の個数は $ 1 $ のままで、メイダイ君の体力は $ 2 $ になります。 $ 1 $ つ目の場合は、家が合計で $ 2 $ 個作られたため、行動を終了します。 $ 2 $ つ目の場合は、続けて確率 $ 1 $ で行動 $ 1 $ を取り、 $ 2 $ 個目の家を作って行動を終了します。 したがって、メイダイ君が家を $ 2 $ 個作るまで行動するとき、 $ \frac{2}{2} \times \frac{1}{2} = \frac{1}{2} $ の確率で木を $ 2 $ 本消費し、 $ \frac{2}{2} \times \frac{1}{2} \times \frac{2}{2} = \frac{1}{2} $ の確率で木を $ 3 $ 本消費することがわかります。 よって家が $ 2 $ 個作られるまでに消費される木の本数の期待値は $ 2 \times \frac{1}{2} + 3 \times \frac{1}{2} = \frac{5}{2} $ であり、 $ 499122179 \times 2 \equiv 5 \pmod{998244353} $ なので $ 499122179 $ が答えになります。 ### Constraints - $ 1 \leq H \leq 3\times10^3 $ - $ 1 \leq K \leq 3\times10^3 $ - 入力される値は全て整数