{"raw_statement":[{"iden":"problem statement","content":"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$.\nHow many strings are there that could be the initial string $S$? Find this count modulo $998244353$."},{"iden":"constraints","content":"*   $3 \\leq |T| \\leq 5000$\n*   $0 \\leq K \\leq 10000$\n*   $T$ is a string consisting of `A`, `R`, and `C`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$T$\n$K$"},{"iden":"sample input 1","content":"ARCCARC\n1"},{"iden":"sample output 1","content":"53\n\nBelow are some examples of the initial string $S$ from which we can get the string $T$ = `ARCCARC` with at most $1$ operation.\n\n*   $S$ = `ARCCARC`: we can choose to do nothing to get `ARCCARC`.\n*   $S$ = `CRACARC`: we can choose the $1$\\-st, $2$\\-nd, $3$\\-rd characters and overwrite them with `ARC` to get `ARCCARC`.\n*   $S$ = `ARCCCCC`: we can choose the $5$\\-th, $6$\\-th, $7$\\-th characters and overwrite them with `ARC` to get `ARCCARC`.\n\nThere are many other strings that could be $S$, for a total of $53$."},{"iden":"sample input 2","content":"ARARCRCA\n5"},{"iden":"sample output 2","content":"2187\n\nIf the intial string $S$ is `AAAAAAAA`, one way to get $T$ = `ARARCRCA` with at most $5$ operations is as follows.\n\n*   Step $1$: choose the $3$\\-rd, $4$\\-th, $5$\\-th characters and overwrite them with `ARC` to get the string `AAARCAAA`.\n*   Step $2$: choose the $5$\\-th, $6$\\-th, $7$\\-th characters and overwrite them with `ARC` to get the string `AAARARCA`.\n*   Step $3$: choose the $1$\\-st, $2$\\-nd, $3$\\-rd characters and overwrite them with `ARC` to get the string `ARCRARCA`.\n*   Step $4$: choose the $3$\\-rd, $4$\\-th, $5$\\-th characters and overwrite them with `ARC` to get the string `ARARCRCA`.\n\nThere are many other strings that could be $S$, for a total of $2187$."},{"iden":"sample input 3","content":"AARCRRARCC\n0"},{"iden":"sample output 3","content":"1\n\nWe can get $T$ = `AARCRRARCC` with $0$ operations in only one case in which $S = T$ from the beginning, or $S$ = `AARCRRARCC`."},{"iden":"sample input 4","content":"AAAAARRRRRCCCCC\n131"},{"iden":"sample output 4","content":"1\n\nIn this case, there is just one string that could be $S$: `AAAAARRRRRCCCCC`."},{"iden":"sample input 5","content":"CAARCACRAAARARARCRCRARCARARCRRARC\n9"},{"iden":"sample output 5","content":"797833187\n\nThere are $320236026147$ strings that could be $S$, so print this count modulo $998244353$, which is $797833187$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}