← 返回题目列表

AtCoder · agc064_d

D. 红色和蓝色芯片

中文机器翻译题面 查看原题

分数: 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