AT_ttpc2023_g Cola

Alice は $ (1,2,\dots,N) $ の順列 $ P=(P_{1},P_{2},\dots,P_{N}) $ がお気に入りです。 $ P $ を当てたら Alice からコーラがもらえることを知った Bob は、Alice に質問をして $ P $ を当てることにしました。 Bob は以下の質問を $ M $ 回まで行うことができます。 - $ (1,2,\dots,N) $ の順列 $ Q=(Q_{1},Q_{2},\dots,Q_{N}) $ をひとつ決め、Alice にお気に入りの順列が $ Q $ であるかを聞く。 ここで $ M \leq N $ が成り立ちます。 Alice は Bob の質問に対して以下の行動を行います。 - $ P = Q $ であるなら、Alice は Bob にコーラをあげる。 - $ P \neq Q $ であるなら、Alice は $ P_{i}\neq Q_{i} $ となる最小の $ i $ を Bob に教える。 例えば、 $ P=(4,3,2,1) $ であるときに $ Q=(4,3,1,2) $ として質問すると、Alice は Bob に「 $ P_{i}\neq Q_{i} $ となる $ i $ が存在して、その $ i $ のうち最も小さいものは $ 3 $ である」ことを教えます。 **$ M $ 回目の質問の後に $ P $ を特定したとしてもコーラはもらえないことに注意してください。** はじめ、Bob は $ P $ についての情報を持っていません。Bob が Alice からコーラをもらえる確率を最大化したときのその確率を $ \text{mod} \;998244353 $ で求めてください。 確率 $ \text{mod} \;998244353 $ の定義 この問題で求める確率は必ず有理数になることが証明できます。また、この問題の制約化では、求める確率を既約分数 $ \frac{y}{x} $ で表したときに $ x $ が $ 998244353 $ で割り切れないことが保証されます。このとき、 $ y \equiv xz \pmod{998244353} $ を満たす $ 0\leq z\lt 998244353 $ がただ一つ存在するので、 $ z $ を出力してください。

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

答えを出力せよ。

### 部分点 - 追加の制約 $ M \leq 10^{5} $ を満たすデータセットに正解した場合は $ 70 $ 点が与えられる。 ### Sample Explanation 1 質問 $ 1 $ 回に対し $ P $ として考えられる順列は $ 2 $ 種類あるので、 $ \frac{1}{2} $ の確率でコーラがもらえます。 **$ 1 $ 回目の質問で外しても $ P $ を特定できますが、コーラはもらえないことに注意してください。** ### Sample Explanation 2 $ 1 $ 回目の質問で必ずコーラがもらえます。 ### Constraints - $ 1 \leq M \leq N \leq 10^{7} $ - 入力は全て整数