分数: 900 点
问题陈述
有 N 正方形:正方形 1,方形 2, \ldots,方形 N。每个方块的颜色为红色或蓝色。
方块的颜色由字符串表示 S 长度 N。具体来说,对于每个
如果 i = 1, 2, \ldots, N,方形 i 为红色,则 i- 第一个字符 S is R,如果是蓝色 B。
广场 N 始终为蓝色。
最初,每个方块都有一个与该方块颜色相同的筹码。
对于每个 i = 1, 2, \ldots, N-1 按照这个顺序,让我们执行以下操作。
- 选择一个整数 j 这样 i \lt j \leq N 和正方形 j 是彩色的 蓝色,并将一堆筹码放在正方形上 i 在广场上的筹码堆顶部 j,保持筹码的顺序。
打印芯片的可能颜色序列数 N- 方形碎片堆 N 经过上述过程从上到下,取模 998244353.
约束
- 2 \leq N \leq 300
- N 是一个整数。
- S 是一个长度为的字符串 N 组成
R和B. - 的 N- 第一个字符 S is
B.
输入
输入由标准输入按以下格式给出:
N S
输出
打印答案。
示例输入 1
4 RBRB
示例输出 1
2
我们使用一个由以下组成的字符串 R 和 B,对应红色和蓝色,表示一堆筹码从上到下的颜色顺序。
特别是,芯片的颜色顺序 0-chip 堆是一个空字符串 \varepsilon.
另外,正方形上的筹码颜色顺序的状态 1, 2, 3, 4 是 S_1, S_2, S_3, S_4分别称为状态 (S_1, S_2, S_3, S_4).
以下过程产量 RRBB 作为正方形上筹码的颜色顺序 4.
- 首先,在每个方格上放置一个与该方格颜色相同的筹码,从而产生状态 (
R,B,R,B). - 将一堆筹码放在正方形上 1 在广场上的筹码堆顶部 2,导致状态 (\varepsilon,
RB,R,B). - 将一堆筹码放在正方形上 2 在广场上的筹码堆顶部 4,导致状态 (\varepsilon, \varepsilon,
R,RBB). - 将一堆筹码放在正方形上 3 在广场上的筹码堆顶部 4,导致状态 (\varepsilon, \varepsilon, \varepsilon,
RRBB).
以下过程产量 RBRB 作为正方形上筹码的颜色顺序 4.
- 首先,在每个方格上放置一个与该方格颜色相同的筹码,从而产生状态 (
R,B,R,B). - 将一堆筹码放在正方形上 1 在广场上的筹码堆顶部 4,导致状态 (\varepsilon,
B,R,RB). - 将一堆筹码放在正方形上 2 在广场上的筹码堆顶部 4,导致状态 (\varepsilon, \varepsilon,
R,BRB). - 将一堆筹码放在正方形上 3 在广场上的筹码堆顶部 4,导致状态 (\varepsilon, \varepsilon, \varepsilon,
RBRB).
以上两个, RRBB 和 RBRB,是正方形上筹码堆的唯一可能的颜色序列 4 从上到下处理完问题后。
示例输入 2
20 RRBRRRBBRBBBBRBRBRBB
示例输出 2
92378