問題文

UT 君と PC 君は Nim というゲームで遊んでいます。$N$ 個の正整数 $A_1, A_2,\ldots, A_N$ に対し、$\mathrm{Nim}(A_1, A_2, \ldots, A_N)$ とは次のゲームのことを指します。

• いくつかの石からなる $N$ 個の山があり、はじめ $i\ (1\le i\le N)$ 番目の山には $A_i$ 個の石がある。UT 君から始めて、$2$ 人は交互に以下の操作を $1$ 回ずつ繰り返す。
• (操作) 石が $1$ 個以上残っている山を $1$ つ選ぶ。その山から石を $1$ 個以上取り除く。
• 石が全て取り除かれた時点でゲームを終了し、最後に操作を行ったプレイヤーを勝ち、もう一方のプレイヤーを負けとする。
• ゲーム開始時点からゲーム終了時点までに $2$ 人が行った操作の回数の合計を $T$ としたとき、勝ったプレイヤーが $10^{100}-T$ 点、負けたプレイヤーが $T-10^{100}$ 点を得る。

$1 \le A_i \le M\ (1\le i\le N)$ を満たす長さ $N$ の整数列 $(A_1, A_2, \ldots, A_N)$ は $M^N$ 通りありますが、その全てに対して、$2$ 人は $1$ 回ずつ $\mathrm{Nim}(A_1, A_2, \ldots, A_N)$ を遊びます。

それぞれが全てのゲームで獲得する点数の合計を最大化するように行動したとき、これら $M^N$ 回のゲームの操作回数の合計は何回になるでしょうか？答えは非常に大きくなる可能性があるので、$998244353$ で割った余りを求めてください。

制約

• 入力は全て整数
• $1 \le N \le 10^{9}$
• $1 \le M \le 500$

入力例 1Copy

2 2

出力例 1Copy

12

$2$ 人は以下の $4$ つのゲームを行います。

• $\mathrm{Nim}(1, 1)$
• $\mathrm{Nim}(1, 2)$
• $\mathrm{Nim}(2, 1)$
• $\mathrm{Nim}(2, 2)$

それぞれが最善を尽くした場合、各ゲームの操作回数はそれぞれ $2$、$3$、$3$、$4$ になります。これらの合計である $12$ を出力します。

入力例 2Copy

4 5

出力例 2Copy

6748

入力例 3Copy

1 222

出力例 3Copy

222

入力例 4Copy

987654321 456

出力例 4Copy

897555885

答えの値を $998244353$ で割った余りを出力してください。