数列の列 $S$ を考える。最初、$S_0 = (1)$ とする。その後、$S_1, S_2, \dots, S_n$ を以下のように構築する。

$|S_i|$ を数列 $S_i$ の長さとし、$s_{i,j}$ を $S_i$ の $j$ 番目の要素とする。このとき、$S_{i+1}$ は長さが $|S_i| + 1$ となり、$S_i$ に対して以下の2つの操作のいずれかを行うことで得られる。

• 新しい数列の $|S_i| + 1$ 番目の要素として、$1$ または与えられた整数 $m$ を書き加える。
• インデックス $j$ ($1 \le j < |S_i|$) を選択し、$s_{i,j} < x < s_{i,j+1}$ または $s_{i,j} > x > s_{i,j+1}$ を満たす整数 $x$ を選び、$s_{i,j}$ と $s_{i,j+1}$ の間に挿入する。これにより、それ以降の要素のインデックスは $1$ ずつ後ろにずれる。

$n$ と $m$ が与えられたとき、異なる順序付きの数列の集合 $S_1, \dots, S_n$ の個数を求めよ。2つの集合は、少なくとも1つの $i$ ($1 \le i \le n$) について $S_i$ が異なるとき、異なるものとみなす。答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力せよ。

入力

入力は1行で構成され、2つの整数 $n$ と $m$ ($1 \le n \le 3000, 2 \le m \le 10^8$) が含まれる。

出力

異なる数列 $S$ の個数を $998\,244\,353$ で割った余りを出力せよ。

入出力例

入力 1

2 3

出力 1

5

入力 2

1024 52689658

出力 2

654836147

注記

最初の例における可能な数列の組み合わせは以下の通りである。

• $S_1 = (1, 3)$ (1つ目の操作)、その後 $S_2 = (1, 2, 3)$ (2つ目の操作)
• $S_1 = (1, 1)$ (1つ目の操作)、その後 $S_2 = (1, 1, 3)$ (1つ目の操作)
• $S_1 = (1, 1)$ (1つ目の操作)、その後 $S_2 = (1, 1, 1)$ (1つ目の操作)
• $S_1 = (1, 3)$ (1つ目の操作)、その後 $S_2 = (1, 3, 3)$ (1つ目の操作)
• $S_1 = (1, 3)$ (1つ目の操作)、その後 $S_2 = (1, 3, 1)$ (1つ目の操作)

したがって、答えは $5$ である。