题目描述

A, R, C からなる文字列 $S$ から始めて、「連続する三文字を選んで ARC に上書きする」操作を $K$ 回以下行ったところ、文字列 $T$ が得られました。

さて、最初の文字列 $S$ として何通りがあり得るでしょうか？これを $998244353$ で割った余りを求めてください。

输入格式

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

$T$ $K$

输出格式

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

题目大意

有一个长度为 $n$ 的字符串 $S$，$S$ 中仅包含 A，R 和 C 三种字符。我们对 $S$ 执行如下操作至多 $k$ 次：选择连续三个字符，修改其为 ARC。最后我们能得到一个字符串 $T$。

给定 $T$，请计数可能作为初始字符串 $S$ 的串。答案对 $998244353$ 取模。

$3\le n\le 5000, 0\le k\le 10000$。

ARCCARC
1

53

ARARCRCA
5

2187

AARCRRARCC
0

1

AAAAARRRRRCCCCC
131

1

CAARCACRAAARARARCRCRARCARARCRRARC
9

797833187

提示

制約

• $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$ を出力してください。