AT_kupc2020_g Counting Angels

[problemUrl]: https://atcoder.jp/contests/kupc2020/tasks/kupc2020_g タプリスちゃんは数列が好きです。 タプリスちゃんは現在、長さ $ 1 $ の数列 $ A\ =\ (1) $ を持っています。 タプリスちゃんは $ A $ に対して、以下のいずれかの操作を選んで行うことを $ N $ 回繰り返すことにしました。以下、数列 $ A $ の前から $ i~(1\ \leq\ i\ \leq\ |A|) $ 番目の要素を $ a_i $ と書くことにします。 - $ A $ の末尾に $ 1 $ または $ M $ を追加する - $ 1\ \leq\ i\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $

数列の列 $ S_1,\ S_2,\ \ldots,\ S_N $ としてありえるものの種類数を $ 998244353 $ で割った余りを出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 3000 $ - $ 2\ \leq\ M\ \leq\ 10^8 $ ### Sample Explanation 1 まず最初の操作で $ 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 $ となります。 ### Sample Explanation 2 $ 998244353 $ で割った余りを出力してください。