配点 : $1000$ 点

問題文

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

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

制約

• $3 \leq |T| \leq 5000$
• $0 \leq K \leq 10000$
• $T$ は A, R, C からなる文字列

入力

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

$T$

$K$

出力

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

ARCCARC
1

53

例えば、最初の文字列 $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$ 通りです。

ARARCRCA
5

2187

最初の文字列 $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$ 通りです。

AARCRRARCC
0

1

$0$ 回の操作で文字列 $T$ = AARCRRARCC を得られるのは、最初の時点で $S = T$ のとき、すなわち $S$ = AARCRRARCC の $1$ 通りしかありません。

AAAAARRRRRCCCCC
131

1

この入力例では、$S$ としてあり得るものは AAAAARRRRRCCCCC の $1$ 通りだけです。

CAARCACRAAARARARCRCRARCARARCRRARC
9

797833187

最初の文字列 $S$ としてあり得るものは $320236026147$ 通りあるので、これを $998244353$ で割った余りである $797833187$ を出力してください。