D - Red and Blue Chips Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

マス 1 、マス 2 、\ldots 、マス N の N 個のマスがあり、各マスは赤と青のどちらかの色で塗られています。 各マスの色は、R と B のみからなる長さ N の文字列 S によって表され、具体的には i = 1, 2, \ldots, N についてマス i は、S の i 文字目が R のとき赤で、B のとき青で塗られています。 また、マス N は必ず青で塗られています。

はじめ、各マスに 1 枚ずつ、マスの色と同じ色のチップが置かれています。

各 i = 1, 2, \ldots, N-1 についてこの順番で下記の操作を行います。

  • i \lt j \leq N かつ マス j が青で塗られているような整数 j を選び、マス i にあるチップの山を、チップの上下の位置関係を維持したまま、マス j にあるチップの山の上に重ねる。

上記の手順を行った後にマス N にできる N 枚のチップからなる山の、各チップの色を山の上のものから順に並べた列としてあり得るものの個数を 998244353 で割った余りを出力してください。

制約

  • 2 \leq N \leq 300
  • N は整数
  • S は R と B のみからなる長さ N の文字列
  • S の N 文字目は B

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを出力せよ。

入力例 1

4
RBRB

出力例 1

2

山の各チップの色を山の上のものから順に並べた列を、赤と青に対応する文字 R と B からなる文字列で表すことにします。 特に、0 枚のチップからなる山の各チップの色を並べた列は、空文字列 \varepsilon です。

また、マス 1, 2, 3, 4 の山の各チップの色を山の上のものから順に並べた列がそれぞれ S_1, S_2, S_3, S_4 である状態を、状態 (S_1, S_2, S_3, S_4) と呼ぶことにします。

下記の手順を行うと、その後にマス 4 にできる山の各チップの色を山の上のものから順に並べた列として、RRBB が得られます。

  • まず、各マスに 1 枚ずつ、マスの色と同じ色のチップを置く。その結果、状態 ( R , B , R , B ) になる。
  • マス 1 にある山を、マス 2 にある山の上に重ねる。その結果、状態 (\varepsilon, RB , R , B ) になる。
  • マス 2 にある山を、マス 4 にある山の上に重ねる。その結果、状態 (\varepsilon, \varepsilon, R , RBB ) になる。
  • マス 3 にある山を、マス 4 にある山の上に重ねる。その結果、状態 (\varepsilon, \varepsilon, \varepsilon, RRBB ) になる。

また、下記の手順を行うと、その後にマス 4 にできる山の各チップの色を山の上のものから順に並べた列として、RBRB が得られます。

  • まず、各マスに 1 枚ずつ、マスの色と同じ色のチップを置く。その結果、状態 ( R , B , R , B ) になる。
  • マス 1 にある山を、マス 4 にある山の上に重ねる。その結果、状態 (\varepsilon, B , R , RB ) になる。
  • マス 2 にある山を、マス 4 にある山の上に重ねる。その結果、状態 (\varepsilon, \varepsilon, R , BRB ) になる。
  • マス 3 にある山を、マス 4 にある山の上に重ねる。その結果、状態 (\varepsilon, \varepsilon, \varepsilon, RBRB ) になる。

問題中の手順を行った後にマス 4 にできる山の、各チップの色を山の上のものから順に並べた列としてあり得るものは、上記の RRBB と RBRB の 2 個のみです。

入力例 2

20
RRBRRRBBRBBBBRBRBRBB

出力例 2

92378

Score : 900 points

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.

Sample Input 1

4
RBRB

Sample 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.

Sample Input 2

20
RRBRRRBBRBBBBRBRBRBB

Sample Output 2

92378