AT_tupc2023_l Random Mex

$ 0 $ 以上 $ M $ 未満の整数を一様ランダムに選ぶという操作を $ N $ 回行います。 $ i $ 回目に選ばれた数を $ A_i $ とするとき $ \mathrm{mex}\big(A_1,A_2,\dots,A_N\big) $ の期待値を $ \text{mod}\,998244353 $ で求めてください。 ただし、 $ \mathrm{mex}\big(A_1,A_2,\dots,A_N\big) $ で $ A_1,A_2,\dots,A_N $ に含まれない最小の非負整数を表します。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。 期待値 $ \text{mod}\,998244353 $ の定義 この問題で求める期待値は必ず有理数になることが証明できます。また、この問題の制約下では、求める期待値を既約分数 $ \frac{y}{x} $ で表したときに $ {x} $ が $ 998244353 $ で割り切れないことが保証されます。 このとき $ xz≡y\;(\text{mod}\,998244353) $ を満たすような $ 0 $ 以上 $ 998244352 $ 以下の整数 $ z $ が一意に定まります。この $ z $ を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースに対する答えを出力せよ。

### 部分点 - 追加の制約 $ T \leq 5,N \leq 100, M \leq 100 $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 ### Sample Explanation 1 - $ 1 $ つ目のテストケースについて、 $ A $ として考えられるものは $ (0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) $ の $ 8 $ つです。それぞれの $ \mathrm{mex} $ の値は $ 1,2,2,2,2,2,2,0 $ なので求める期待値は $ \dfrac{13}{8} $ です。 - $ 2 $ つ目のテストケースについて、 $ A $ として考えられるものは $ (0) $ のみです。よって求める期待値は $ 1 $ です。 ### Constraints - $ 1 \leq T \leq 3 \times 10^5 $ - $ 1 \leq N,M \leq 8000 $ - 入力はすべて整数