AtCoder Grand Contest 064
D
Red and Blue Chips
AtCoder
⌀ 2808
原题
← CE →
翻译中…

Problem Statement

翻译中…

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.

翻译中…

Initially, each square has a chip of the same color as the square.

翻译中…

For each $i = 1, 2, \ldots, N-1$ in this order, let us perform the following operation.

翻译中…
  • 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.
翻译中…

Print 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$.

翻译中…

Constraints

翻译中…
  • $2 \leq N \leq 300$
  • $N$ is an integer.
  • $S$ is a string of length $N$ consisting of R and B.
  • The $N$-th character of $S$ is B.
翻译中…

Input

翻译中…

The input is given from Standard Input in the following format:

翻译中…

N
S

翻译中…

Output

翻译中…

Print the answer.

翻译中…

样例

Input #1
4
RBRB
Output #1
2
We 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$. Also, 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)$. The following process yields `RRBB` as the sequence of colors of chips of the pile on square $4$. - First, on each square, place a chip of the same color as the square, resulting in state $($ `R` $,$ `B` $,$ `R` $,$ `B` $)$. - 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` $)$. - 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` $)$. - 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` $)$. The following process yields `RBRB` as the sequence of colors of chips of the pile on square $4$. - First, on each square, place a chip of the same color as the square, resulting in state $($ `R` $,$ `B` $,$ `R` $,$ `B` $)$. - 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` $)$. - 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` $)$. - 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` $)$. The 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.
Input #2
20
RRBRRRBBRBBBBRBRBRBB
Output #2
92378
题目信息
题号
agc064_d
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。