当前没有测试数据。

删除人员

分数：600

---

问题描述

编号为1到N的N个人围成一圈，按顺时针顺序排列在一起。每个人的朝向由长度为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$。

求总成本的期望值，对$998244353$取模。

---

注意事项

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

---

约束条件

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

---

输入

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

$N$

$S$

---

输出

打印答案。

---

输入样例1

3
LLR

输出样例1

831870297

所求的期望值是$\frac{17}{6}$。我们有$831870297 \times 6 \equiv 17\pmod{998244353}$，所以应该打印出$831870297$。

供参考的一种可能的情况如下：

1. 选择第2个人。从第2个人所看到的剩余圈子中，最近的人是第1个人，将其从圈子中删除。
2. 再次选择第2个人。从第2个人所看到的剩余圈子中，最近的人是第3个人，将其从圈子中删除。

在这种情况下，总成本为3（等于1+2）。

---

输入样例2

10
RRRRRRLLRR

输出样例2

460301586