Time Limit : sec, Memory Limit : KB
Japanese

J: 左崎・右男

問題文

左崎さんと右男さんは、長さ $N$ の数列 $a_1, a_2, \dots ,a_n$ を使ったゲームで遊ぶのが好きです。 このゲームでは左崎さんと右男さんで交互に以下の操作を行います。

  • 左崎さんの手番では $1 \leq k \leq n$ を指定し、$a_1, a_2, \dots ,a_k$ の値をそれぞれ $1$ ずつ減らす。
  • 右男さんの手番では $1 \leq k \leq n$ を指定し、$a_k, a_{k+1}, \dots ,a_n$ の値をそれぞれ $1$ ずつ減らす。

手番終了時に数列の中に負の数が存在していた場合、その操作をした人は負けます。負けなかった方は勝ちます。最初に操作をするのは左崎さんです。

左崎さんはこのゲームをプレイするために、$0, 1, \dots, S$ からなる長さ $N$ の数列を全種類($(S+1)^N$ 通り)買ってきました。左崎さんと右男さんがこれらの数列を使って $1$ 回ずつゲームをしました。左崎さんが勝った回数を $998244353$ で割ったあまりを求めてください。ただし、両者ともそれぞれが勝つために最適な操作をしたとします。

制約

  • 入力は全て整数
  • $2 \leq N \leq 1000$
  • $1 \leq S \leq 10^9$

入力

入力は以下の形式で標準入力から与えられます。

$N$ $S$

出力

全ての数列を使って $1$ 回ずつゲームをしたときに、左崎さんが勝った回数を $998244353$ で割ったあまりを出力してください。

入出力例

入力例1

2 1

出力例1

2

左崎さんが買ってきた数列は (0, 0), (0, 1), (1, 0), (1, 1) の $4$ つです。

(0, 0), (0, 1) を使ったゲームでは、左崎さんは最初の手番でどの $k$ を選んでも負けます。 (1, 0) を使ったゲームでは、左崎さんは $k = 1$ を選べば、数列が (0, 0) となり、勝てます。 (1, 1) を使ったゲームでは、左崎さんは $k = 2$ を選べば、数列が (0, 0) となり、勝てます。

入力例2

3 2

出力例2

12

左崎さんが勝つ数列は以下の $12$ 個です。

(1,0,0)
(1,1,0)
(1,1,1)
(1,2,0)
(1,2,1)
(2,0,0)
(2,0,1)
(2,1,0)
(2,1,1)
(2,1,2)
(2,2,0)
(2,2,1)

入力例3

1000 1000000000

出力例3

972070366