AT_arc188_a [ARC188A] ABC Symmetry

[problemUrl]: https://atcoder.jp/contests/arc188/tasks/arc188_a `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 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ S $

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

### 制約 - $ 1\ \leq\ N\ \leq\ 50 $ - $ 0\ \leq\ K\ \leq\ N(N+1)/2 $ - $ N,K $ は整数である - $ |S|=N $ - $ S $ は `A`, `B`, `C`, `?` からなる文字列である ### Sample Explanation 1 `?` を `A`, `B`, `C` に置き換えてできる文字列は `AAAB`, `ABAB`, `ACAB` の $ 3 $ つあります。 このうち `AAAB` は $ 1,2 $ 文字目の `AA` および $ 2,3 $ 文字目の `AA` がよい文字列であるため、連続する部分文字列としてよい文字列を $ 2 $ 個含みます。ここで、同じ文字列であるような部分文字列であっても、元の文字列内での位置が異なる場合は別々に数えることに注意してください。 一方、`ABAB` が含むよい文字列は `ABAB` の $ 1 $ 個のみです。また、`ACAB` も `CAB` の $ 1 $ 個しかよい文字列を含みません。 ### Sample Explanation 2 答えを $ 998244353 $ で割った余りを出力してください。