AT_arc131_f [ARC131F] ARC Stamp

[problemUrl]: https://atcoder.jp/contests/arc131/tasks/arc131_f `A`, `R`, `C` からなる文字列 $ S $ から始めて、「連続する三文字を選んで `ARC` に上書きする」操作を $ K $ 回以下行ったところ、文字列 $ T $ が得られました。 さて、最初の文字列 $ S $ として何通りがあり得るでしょうか？これを $ 998244353 $ で割った余りを求めてください。

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

答えを出力してください。

### 制約 - $ 3\ \leq\ |T|\ \leq\ 5000 $ - $ 0\ \leq\ K\ \leq\ 10000 $ - $ T $ は `A`, `R`, `C` からなる文字列 ### Sample Explanation 1 例えば、最初の文字列 $ S $ が次のようなとき、$ 1 $ 回以下の操作で文字列 $ T $ = `ARCCARC` を得ることができます。 - $ S $ = `ARCCARC` のとき：操作を行わないでも文字列 `ARCCARC` が得られる． - $ S $ = `CRACARC` のとき：$ S $ の $ 1,\ 2,\ 3 $ 文字目を選んで `ARC` に上書きすると、文字列 `ARCCARC` が得られる。 - $ S $ = `ARCCCCC` のとき：$ S $ の $ 5,\ 6,\ 7 $ 文字目を選んで `ARC` に上書きすると、文字列 `ARCCARC` が得られる。 上に挙げたもの以外にもたくさんあり、$ S $ としてあり得るものは全部で $ 53 $ 通りです。 ### Sample Explanation 2 最初の文字列 $ S $ が `AAAAAAAA` のとき、例えば次のような $ 5 $ 回以下の操作で文字列 $ T $ = `ARARCRCA` を得ることができます。 - ステップ $ 1 $：まず、$ 3,\ 4,\ 5 $ 文字目を選んで `ARC` に上書きすると、文字列 `AAARCAAA` が得られる。 - ステップ $ 2 $：次に、$ 5,\ 6,\ 7 $ 文字目を選んで `ARC` に上書きすると、文字列 `AAARARCA` が得られる。 - ステップ $ 3 $：次に、$ 1,\ 2,\ 3 $ 文字目を選んで `ARC` に上書きすると、文字列 `ARCRARCA` が得られる。 - ステップ $ 4 $：最後、$ 3,\ 4,\ 5 $ 文字目を選んで `ARC` に上書きすると、文字列 `ARARCRCA` が得られる。 それ以外にも $ S $ としてあり得るものはたくさんあり、全部で $ 2187 $ 通りです。 ### Sample Explanation 3 $ 0 $ 回の操作で文字列 $ T $ = `AARCRRARCC` を得られるのは、最初の時点で $ S\ =\ T $ のとき、すなわち $ S $ = `AARCRRARCC` の $ 1 $ 通りしかありません。 ### Sample Explanation 4 この入力例では、$ S $ としてあり得るものは `AAAAARRRRRCCCCC` の $ 1 $ 通りだけです。 ### Sample Explanation 5 最初の文字列 $ S $ としてあり得るものは $ 320236026147 $ 通りあるので、これを $ 998244353 $ で割った余りである $ 797833187 $ を出力してください。