移除人员

题目描述

编号为 $1$ 到 $N$ 的 $N$ 个人按顺时针顺序站成一圈,顺序为人 $1$,人 $2$,$\cdots$,人 $N$。

每个人面向的方向由长度为 $N$ 的字符串 $S$ 给出。对于每个 $i$ $(1 \leq i \leq N)$,如果 $S_i =$ L,则人 $i$ 面向逆时针方向;如果 $S_i =$ R,则人 $i$ 面向顺时针方向。

以下操作将重复执行 $N-1$ 次。

以等概率从剩余的人中选择一个人,然后从圆圈中移除被选之人所看到的最靠近的人。

此时产生的代价等于从被选之人到被移除之人的距离。

这里,人 $i$ 到人 $j$ $(i \neq j)$ 的距离定义如下。

当人 $i$ 面向顺时针方向时:

• 若 $i \lt j$,距离为 $j-i$;
• 若 $i \gt j$,距离为 $j-i+N$。

当人 $i$ 面向逆时针方向时:

• 若 $i \lt j$,距离为 $i-j+N$;
• 若 $i \gt j$,距离为 $i-j$。

求产生的总代价的期望值,对 $998244353$ 取模(参见提示)。

输入格式

输入按以下格式从标准输入给出:

$N$
$S$

输出格式

输出答案。

样例

3
LLR

831870297

所求期望值为 $\frac{17}{6}$。由于 $831870297 \times 6 \equiv 17\pmod{998244353}$,所以应输出 $831870297$。

作为参考,这里给出一种可能的流程。

人 2 被选中。人 2 在圆圈中看到的最靠近的人是 人 1,人 1 被移出圆圈。

人 2 再次被选中。人 2 在圆圈中看到的最靠近的人是 人 3,人 3 被移出圆圈。

此时产生的总代价为 $3(=1+2)$。

10
RRRRRRLLRR

460301586

数据范围

• $2 \leq N \leq 300$
• $N$ 是整数。
• $S$ 是由 L 和 R 组成的长度为 $N$ 的字符串。

提示

可以证明所求期望值总是有理数。此外,在本问题的约束条件下,当该值用两个互质的整数 $P$ 和 $Q$ 表示为 $\frac{P}{Q}$ 时,存在唯一的整数 $R$ 使得 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。求出这个 $R$。