{"problem":{"name":"ARC Stamp","description":{"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$. How ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc131_f"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $3 \\leq |T| \\leq 5000$\n*   $0 \\leq K \\leq 10000$\n*   $T$ is a string consisting of `A`, `R`, and `C`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$T$\n$K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc131_f","tags":[],"sample_group":[["ARCCARC\n1","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$."],["ARARCRCA\n5","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$."],["AARCRRARCC\n0","1\n\nWe can get $T$ = `AARCRRARCC` with $0$ operations in only one case in which $S = T$ from the beginning, or $S$ = `AARCRRARCC`."],["AAAAARRRRRCCCCC\n131","1\n\nIn this case, there is just one string that could be $S$: `AAAAARRRRRCCCCC`."],["CAARCACRAAARARARCRCRARCARARCRRARC\n9","797833187\n\nThere are $320236026147$ strings that could be $S$, so print this count modulo $998244353$, which is $797833187$."]],"created_at":"2026-03-03 11:01:13"}}