F - ARC Stamp Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 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

出力

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

入力例 1

ARCCARC
1

出力例 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 通りです。

入力例 2

ARARCRCA
5

出力例 2

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 通りです。

入力例 3

AARCRRARCC
0

出力例 3

1

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

入力例 4

AAAAARRRRRCCCCC
131

出力例 4

1

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

入力例 5

CAARCACRAAARARARCRCRARCARARCRRARC
9

出力例 5

797833187

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

Score : 1000 points

Problem Statement

On a string S consisting of A, R, and C, we did the following operation at most K times: choose three consecutive characters and overwrite them with ARC. The result is the string T.

How many strings are there that could be the initial string S? Find this count modulo 998244353.

Constraints

  • 3 \leq |T| \leq 5000
  • 0 \leq K \leq 10000
  • T is a string consisting of A, R, and C.

Input

Input is given from Standard Input in the following format:

T
K

Output

Print the answer.

Sample Input 1

ARCCARC
1

Sample Output 1

53

Below are some examples of the initial string S from which we can get the string T = ARCCARC with at most 1 operation.

  • S = ARCCARC: we can choose to do nothing to get ARCCARC.
  • S = CRACARC: we can choose the 1-st, 2-nd, 3-rd characters and overwrite them with ARC to get ARCCARC.
  • S = ARCCCCC: we can choose the 5-th, 6-th, 7-th characters and overwrite them with ARC to get ARCCARC.

There are many other strings that could be S, for a total of 53.

Sample Input 2

ARARCRCA
5

Sample Output 2

2187

If the intial string S is AAAAAAAA, one way to get T = ARARCRCA with at most 5 operations is as follows.

  • Step 1: choose the 3-rd, 4-th, 5-th characters and overwrite them with ARC to get the string AAARCAAA.
  • Step 2: choose the 5-th, 6-th, 7-th characters and overwrite them with ARC to get the string AAARARCA.
  • Step 3: choose the 1-st, 2-nd, 3-rd characters and overwrite them with ARC to get the string ARCRARCA.
  • Step 4: choose the 3-rd, 4-th, 5-th characters and overwrite them with ARC to get the string ARARCRCA.

There are many other strings that could be S, for a total of 2187.

Sample Input 3

AARCRRARCC
0

Sample Output 3

1

We can get T = AARCRRARCC with 0 operations in only one case in which S = T from the beginning, or S = AARCRRARCC.

Sample Input 4

AAAAARRRRRCCCCC
131

Sample Output 4

1

In this case, there is just one string that could be S: AAAAARRRRRCCCCC.

Sample Input 5

CAARCACRAAARARARCRCRARCARARCRRARC
9

Sample Output 5

797833187

There are 320236026147 strings that could be S, so print this count modulo 998244353, which is 797833187.