問題文

$1$ から $10^{100}$ の番号がついた $10^{100}$ 枚のカードがあり、カード $i$ が 上から $i$ 番目になるように積まれています。 また、空の袋が $1$ 個あります。以下の操作をちょうど $M$ 回行うことを考えます。

上から $K$ 枚のカードを見て、カードを $0$ 枚以上好きな枚数選び、それらを袋に入れる。選ばれなかったカードは相対順序を保ったまま戻す。

操作終了後に袋に入っているカードの集合として考えられるもの全てに対する要素数の総和を $998244353$ で割った余りを求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 入力は全て整数
• $1 \leq T \leq 10^5$
• $1 \leq K <998244353$
• $1 \leq M < 998244353$

入力例 1Copy

3
2 1
3 2
20250308 410338673

出力例 1Copy

4
81
509595821

$1$ 番目のテストケースについて、袋の中に入ったカードの集合としてありうるものは $\lbrace \rbrace, \lbrace 1 \rbrace, \lbrace 2\rbrace, \lbrace 1,2 \rbrace$ で、要素数の総和は $4$ です。