問題文

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

入力例 1

2 2

出力例 1

12

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

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

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

入力例 2

4 5

出力例 2

6748

入力例 3

1 222

出力例 3

222

入力例 4

987654321 456

出力例 4

897555885

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