AT_abc238_h [ABC238Ex] Removing People

[problemUrl]: https://atcoder.jp/contests/abc238/tasks/abc238_h $ 1 $ から $ N $ までの番号を付けられた $ N $ 人の人が、人 $ 1 $、人 $ 2 $、$ \cdots $、人 $ N $ の順に時計回りに円環状に等間隔に並んでいます。 それぞれの人が向いている方向は `L` または `R` のみからなる長さ $ N $ の文字列 $ S $ で表されます。各 $ i\ \,\ (1\ \leq\ i\ \leq\ N) $ に対し、$ S_i\ = $ `L` ならば人 $ i $ は反時計回りの方向を向いており、$ S_i\ = $ `R` ならば人 $ i $ は時計回りの方向を向いています。 以下の操作を $ N-1 $ 回繰り返します。 - 残っている人の中から等確率で一人を選び、その人から見て一番手前にいる残っている人を円環から除く。このとき、選んだ人から除かれる人までの距離と同じだけのコストがかかる。 ここで、人 $ i $ から人 $ j $ $ (i\ \neq\ j) $ までの距離を以下のように定義します。 1. 人 $ i $ が時計回りの方向を向いている場合 - $ i\ \lt\ j $ ならば $ j-i $ - $ i\ \gt\ j $ ならば $ j-i+N $ 2. 人 $ i $ が反時計回りの方向を向いている場合 - $ i\ \lt\ j $ ならば $ i-j+N $ - $ i\ \gt\ j $ ならば $ i-j $ 合計コストの期待値を$ \mod\ 998244353 $ で求めてください（注記参照）。

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

答えを出力せよ。

### 注記 求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $ 2 $ つの整数 $ P $, $ Q $ を用いて $ \frac{P}{Q} $ と表したとき、$ R\ \times\ Q\ \equiv\ P\pmod{998244353} $ かつ $ 0\ \leq\ R\ \lt\ 998244353 $ を満たす整数 $ R $ がただ一つ存在することが証明できます。この $ R $ を求めてください。 ### 制約 - $ 2\ \leq\ N\ \leq\ 300 $ - $ N $ は整数 - $ S $ は `L` と `R` のみからなる長さ $ N $ の文字列 ### Sample Explanation 1 求める期待値は $ \frac{17}{6} $ です。$ 831870297\ \times\ 6\ \equiv\ 17\pmod{998244353} $ ですので、$ 831870297 $ を出力します。 なお、例えば以下のような操作手順が考えられます。 1. 人 $ 2 $ を選ぶ。人 $ 2 $ から見て一番手前にいる、円環に残っている人は人 $ 1 $ であるため、人 $ 1 $ を円環から除く。 2. 人 $ 2 $ をもう一度選ぶ。人 $ 2 $ から見て一番手前にいる、円環に残っている人は人 $ 3 $ であるため、人 $ 3 $ を円環から除く。 この操作手順における合計コストは $ 3(=1+2) $ となります。