問題文

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 で求めてください。

制約

• 1 \leq M \leq N \leq 10^{7}
• 入力は全て整数

部分点

• 追加の制約 M \leq 10^{5} を満たすデータセットに正解した場合は 70 点が与えられる。

入力例 1

2 1

出力例 1

499122177

質問 1 回に対し P として考えられる順列は 2 種類あるので、\frac{1}{2} の確率でコーラがもらえます。

1 回目の質問で外しても P を特定できますが、コーラはもらえないことに注意してください。

入力例 2

1 1

出力例 2

1

1 回目の質問で必ずコーラがもらえます。

入力例 3

167 91

出力例 3

469117530