問題文

タプリスちゃんは数列が好きです。

タプリスちゃんは現在、長さ 1 の数列 A = (1) を持っています。

タプリスちゃんは A に対して、以下のいずれかの操作を選んで行うことを N 回繰り返すことにしました。以下、数列 A の前から i~(1 \leq i \leq |A|) 番目の要素を a_i と書くことにします。

• A の末尾に 1 または M を追加する
• 1 \leq i < |A| である整数 i を 1 つ選択する。a_i < x < a_{i + 1} または a_i > x > a_{i + 1} が成り立つような整数 x を a_i と a_{i + 1} の間に追加する

i 回目の操作を行ったあとの数列 A を S_i と書くことにします。

数列の列 S_1, S_2, \ldots, S_N としてありえるものの種類数を 998244353 で割った余りを求めてください。

制約

• 1 \leq N \leq 3000
• 2 \leq M \leq 10^8

入力例 1

2 3

出力例 1

5

まず最初の操作で A の末尾に 3 を追加すると、A = (1, 3) となります。

次に 2 回目の操作で A の 1 と 3 の間に 2 を追加すると、A = (1, 2, 3) となります。

よってこのように操作を行ったとき、S_1 = (1, 3), S_2 = (1, 2, 3) となります。

この他に考えられるのは、

• S_1 = (1, 1), S_2 = (1, 1, 1) となる場合
• S_1 = (1, 1), S_2 = (1, 1, 3) となる場合
• S_1 = (1, 3), S_2 = (1, 3, 3) となる場合
• S_1 = (1, 3), S_2 = (1, 3, 1) となる場合

の 4 通りです。よって答えは 5 となります。

入力例 2

1024 52689658

出力例 2

654836147

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