题目描述

有$N$个人，编号为$1$到$N$，站在一个圆圈上，按逆时针顺序为Person $1$，Person $2$，$\dots$，Person $N$。每个人的面向由长度为$N$的字符串$S$给出。对于每个$i$ $(1 \le i \le N)$，如果$S_i =$ L，则Person $i$面向顺时针方向，如果$S_i =$ R，则Person $i$面向逆时针方向。

接下来的操作将重复$N-1$次。

• 以相等的概率选择剩余的人之一，并从所选人看到的最近的人中移除，这样会产生一个与所选人到被移除人的距离相等的成本。

在这里，从Person $i$到Person $j$ $(i \neq j)$的距离定义如下。

1. 当Person $i$面向顺时针方向时：
   • 如果 $i < j$，则距离为$j-i$；
   • 如果 $i > j$，则距离为$j-i+N$。
2. 当Person $i$面向逆时针方向时：
   • 如果 $i < j$，则距离为$i-j+N$；
   • 如果 $i > j$，则距离为$i-j$。

求期望值的总成本，对$998244353$取模（参见注释）。

注释

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

约束条件

• $2 \le N \le 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. 选择Person $2$。从圈中剩下的人中，Person $2$看到的最近的人是Person $1$，将其从圈中移除。
2. 再次选择Person $2$。从圈中剩下的人中，Person $2$看到的最近的人是Person $3$，将其从圈中移除。

在这种情况下，总成本为$3(=1+2)$。

示例输入2

10
RRRRRRLLRR

示例输出2

460301586