{"raw_statement":[{"iden":"problem statement","content":"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.\n\n*   Operation $1$: Choose two identical characters in the string and delete them (cannot be performed if there are not two or more identical characters).\n*   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`).\n\nFor example, `ABACA` is a good string because it can be turned into an empty string by performing the operations as follows:\n\n*   Choose the 2nd, 4th, and 5th characters and delete them (Operation $2$). The string becomes `AA`.\n*   Choose the 1st and 2nd characters and delete them (Operation $1$). The string becomes an empty string.\n\nYou 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.\nFind the count modulo $998244353$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 50$\n*   $0 \\leq K \\leq \\frac{N(N+1)}{2}$\n*   $N$ and $K$ are integers.\n*   $|S| = N$\n*   $S$ is a string consisting of `A`, `B`, `C`, and `?`."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $K$\n$S$"},{"iden":"sample input 1","content":"4 2\nA?AB"},{"iden":"sample output 1","content":"1\n\nBy replacing `?` with `A`, `B`, or `C`, we can obtain the following three strings: `AAAB`, `ABAB`, `ACAB`.\nAmong 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.\nOn the other hand, `ABAB` contains only one good substring `ABAB`. Also, `ACAB` contains only one good substring `CAB`."},{"iden":"sample input 2","content":"50 411\n??AB??C???????????????????????????????A???C????A??"},{"iden":"sample output 2","content":"457279314\n\nPrint the count modulo $998244353$."},{"iden":"sample input 3","content":"1 0\nA"},{"iden":"sample output 3","content":"1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}