题目描述

$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$

输出格式

答えを出力せよ。

题目大意

给定一个环形排列的 $N$ 个人，每个人朝向左或右。定义从第 $i$ 个人到第 $j$ 个人的距离为如下值之一：

• 如果第 $i$ 个人和第 $j$ 个人都朝向左并且 $i<j$ 或者都朝向右并且 $i>j$，那么距离为 $j-i$。
• 如果第 $i$ 个人朝向左，第 $j$ 个人朝向右，并且 $i<j$，那么距离为 $N+i-j$。
• 如果第 $i$ 个人朝向右，第 $j$ 个人朝向左，并且 $i>j$，那么距离为 $N+j-i$。

执行以下操作 $N-1$ 次，每次选择当前剩余人员中的一个人并将该人前面最近的人从环形排列中移除（即被移除的人要求与该人距离相同），移除时需要支付与两个人距离相等的代价。

求所有操作完成后所需支付的代价的期望值，结果对 $998244353$ 取模。

3
LLR

831870297

10
RRRRRRLLRR

460301586

提示

注記

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $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)$ となります。