AT_agc064_d [AGC064D] Red and Blue Chips

[problemUrl]: https://atcoder.jp/contests/agc064/tasks/agc064_d マス $ 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 $ で割った余りを出力してください。

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

答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 300 $ - $ N $ は整数 - $ S $ は `R` と `B` のみからなる長さ $ N $ の文字列 - $ S $ の $ N $ 文字目は `B` ### Sample Explanation 1 山の各チップの色を山の上のものから順に並べた列を、赤と青に対応する文字 `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 $ 個のみです。