A - ABC Symmetry Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

A, B, C からなる空でない文字列 T に対して、以下の 2 種類の操作を好きな順で好きな回数だけ行い、空文字列とすることができる時、これを「よい文字列」と呼びます。

  • 操作 1 ：文字列に存在する同一の文字を 2 つ選び、削除する（同一の文字が 2 つ以上ない場合は行えない）
  • 操作 2 ：文字列に存在する A, B, C を 1 つずつ選び、削除する（A, B, C がそれぞれ 1 つ以上ない場合は行えない）

例えば、ABACA は、次のように操作を行うことで空文字列にできるため、よい文字列です。

  • 2,4,5 文字目を選んで削除する（操作 2）。文字列は AA になる。
  • 1,2 文字目を選んで削除する（操作 1）。文字列は空文字列になる。

A, B, C, ? からなる長さ N の文字列 S が与えられます。? をそれぞれ A, B, C のいずれかに置き換えてできる文字列であって、よい文字列を連続する部分文字列として K 個以上含むものはいくつあるでしょうか。ただし、同じ文字列であるような部分文字列であっても、元の文字列内での位置が異なる場合は別々に数えます。

答えを 998244353 で割った余りを求めてください。

制約

  • 1 \leq N \leq 50
  • 0 \leq K \leq N(N+1)/2
  • N,K は整数である
  • |S|=N
  • S は A, B, C, ? からなる文字列である

入力

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

N K
S

出力

答えを 998244353 で割った余りを整数で出力せよ。

入力例 1

4 2
A?AB

出力例 1

1

? を A, B, C に置き換えてできる文字列は AAAB, ABAB, ACAB の 3 つあります。

このうち AAAB は 1,2 文字目の AA および 2,3 文字目の AA がよい文字列であるため、連続する部分文字列としてよい文字列を 2 個含みます。ここで、同じ文字列であるような部分文字列であっても、元の文字列内での位置が異なる場合は別々に数えることに注意してください。

一方、ABAB が含むよい文字列は ABAB の 1 個のみです。また、ACAB も CAB の 1 個しかよい文字列を含みません。

入力例 2

50 411
??AB??C???????????????????????????????A???C????A??

出力例 2

457279314

答えを 998244353 で割った余りを出力してください。

入力例 3

1 0
A

出力例 3

1

Score : 500 points

Problem Statement

For a non-empty string T consisting of A, B, and C, we call it a good string if it can be turned into an empty string by performing the following two types of operations any number of times in any order.

  • Operation 1: Choose two identical characters in the string and delete them (cannot be performed if there are not two or more identical characters).
  • Operation 2: Choose one A, one B, and one C in the string and delete them (cannot be performed if there are not one or more of each of A, B, and C).

For example, ABACA is a good string because it can be turned into an empty string by performing the operations as follows:

  • Choose the 2nd, 4th, and 5th characters and delete them (Operation 2). The string becomes AA.
  • Choose the 1st and 2nd characters and delete them (Operation 1). The string becomes an empty string.

You are given a string S of length N consisting of A, B, C, and ?. How many ways are there to replace each ? with A, B, or C to form a string that contains at least K good strings as contiguous substrings? Substrings are counted separately if they are at different positions in the original string, even if they are identical strings.

Find the count modulo 998244353.

Constraints

  • 1 \leq N \leq 50
  • 0 \leq K \leq \frac{N(N+1)}{2}
  • N and K are integers.
  • |S| = N
  • S is a string consisting of A, B, C, and ?.

Input

The input is given from Standard Input in the following format:

N K
S

Output

Print the answer modulo 998244353.

Sample Input 1

4 2
A?AB

Sample Output 1

1

By replacing ? with A, B, or C, we can obtain the following three strings: AAAB, ABAB, ACAB.

Among these, AAAB contains two good substrings: the AA at positions 1,2 and the AA at positions 2,3. Note that even if the substrings are identical as strings, they are counted separately if they are at different positions in the original string.

On the other hand, ABAB contains only one good substring ABAB. Also, ACAB contains only one good substring CAB.

Sample Input 2

50 411
??AB??C???????????????????????????????A???C????A??

Sample Output 2

457279314

Print the count modulo 998244353.

Sample Input 3

1 0
A

Sample Output 3

1