{"problem":{"name":"Red and Blue Chips","description":{"content":"There are $N$ squares: square $1$, square $2$, $\\ldots$, square $N$. Each square is colored red or blue. The colors of the squares are represented by a string $S$ of length $N$. Specifically, for each","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc064_d"},"statements":[{"statement_type":"Markdown","content":"There are $N$ squares: square $1$, square $2$, $\\ldots$, square $N$. Each square is colored red or blue. The colors of the squares are represented by a string $S$ of length $N$. Specifically, for each $i = 1, 2, \\ldots, N$, square $i$ is colored red if the $i$\\-th character of $S$ is `R`, and blue if it is `B`. Square $N$ is always colored blue.\nInitially, each square has a chip of the same color as the square.\nFor each $i = 1, 2, \\ldots, N-1$ in this order, let us perform the following operation.\n\n*   Choose an integer $j$ such that $i \\lt j \\leq N$ and square $j$ is colored **blue**, and place the pile of chips on square $i$ on top of the pile of chips on square $j$, keeping the order of the chips.\n\nPrint the number of possible sequences of colors of chips of the $N$\\-chip pile on square $N$ from top to bottom after the above process, modulo $998244353$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 300$\n*   $N$ is an integer.\n*   $S$ is a string of length $N$ consisting of `R` and `B`.\n*   The $N$\\-th character of $S$ is `B`.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc064_d","tags":[],"sample_group":[["4\nRBRB","2\n\nWe use a string consisting of `R` and `B`, corresponding to red and blue, to represent the sequence of colors of the chips of a pile from top to bottom. Particularly, the sequence of colors of the chips of a $0$\\-chip pile is an empty string $\\varepsilon$.\nAlso, the state where the sequences of colors of chips of the piles on square $1, 2, 3, 4$ are $S_1, S_2, S_3, S_4$, respectively, is called as state $(S_1, S_2, S_3, S_4)$.\nThe following process yields `RRBB` as the sequence of colors of chips of the pile on square $4$.\n\n*   First, on each square, place a chip of the same color as the square, resulting in state $($ `R` $, $ `B` $, $ `R` $, $ `B` $)$.\n*   Place the pile of chips on square $1$ on top of the pile of chips on square $2$, resulting in state $(\\varepsilon, $ `RB` $, $ `R` $, $ `B` $)$.\n*   Place the pile of chips on square $2$ on top of the pile of chips on square $4$, resulting in state $(\\varepsilon, \\varepsilon, $ `R` $, $ `RBB` $)$.\n*   Place the pile of chips on square $3$ on top of the pile of chips on square $4$, resulting in state $(\\varepsilon, \\varepsilon, \\varepsilon, $ `RRBB` $)$.\n\nThe following process yields `RBRB` as the sequence of colors of chips of the pile on square $4$.\n\n*   First, on each square, place a chip of the same color as the square, resulting in state $($ `R` $, $ `B` $, $ `R` $, $ `B` $)$.\n*   Place the pile of chips on square $1$ on top of the pile of chips on square $4$, resulting in state $(\\varepsilon, $ `B` $, $ `R` $, $ `RB` $)$.\n*   Place the pile of chips on square $2$ on top of the pile of chips on square $4$, resulting in state $(\\varepsilon, \\varepsilon, $ `R` $, $ `BRB` $)$.\n*   Place the pile of chips on square $3$ on top of the pile of chips on square $4$, resulting in state $(\\varepsilon, \\varepsilon, \\varepsilon, $ `RBRB` $)$.\n\nThe above two, `RRBB` and `RBRB`, are the only possible sequences of colors of chips of the pile on square $4$ from top to bottom after the process in the problem."],["20\nRRBRRRBBRBBBBRBRBRBB","92378"]],"created_at":"2026-03-03 11:01:14"}}