\(N\) 人の人を円環から除かれる順に並べた列を \((P_1,P_2,\ldots,P_{N-1},P_N)\) としましょう。ここで \(P_N\) は最後まで除かれない人のことを指します。すると明らかに、\(P\) は \((1,2,\ldots,N)\) の順列となります。

\(P\) を逆順に見ていくことを考えます。すると、この問題は何もない円環上に人 \(P_N\)、人 \(P_{N-1}\)、\(\cdots\)、人 \(P_1\) をこの順に配置していく問題となります。形式化すると以下の通りです。

何もない円環上に人 \(P_N\)、人 \(P_{N-1}\)、\(\cdots\)、人 \(P_1\) をこの順に配置していく。

この際配置された人は「時計回り！」か「反時計回り！」かのどちらかを叫ぶ必要があり、前者を叫んだ場合は配置された人から見て（配置済みの人のうち）時計回りの方向に隣である人は反時計回りの方向を向いている必要がある。後者も同様である。そして、コストに配置された人からその人までの距離が加算される。

あり得るすべての配置手順（\(P\) の内容 + 各人がどちらの向きを叫んだか）について合計コストを求め、その総和を \(N!\) で割った上で\(\mod 998244353\) で出力せよ。

\(\text{num}[l][r]\) を、人 \(l\) と人 \(r\) が配置済みであり、かつその間には人が一人も配置されていないような状態から人 \(l+1\)、人 \(l+2\)、\(\cdots\)、人 \(r-1\) を配置していく手順の個数と定義します。

同様に、\(\text{cost}[l][r]\) を、人 \(l\) と人 \(r\) が配置済みであり、かつその間には人が一人も配置されていないような状態から人 \(l+1\)、人 \(l+2\)、\(\cdots\)、人 \(r-1\) を配置していく際にかかる合計コストの総和と定義します。

すると、遷移は以下のようになります。イメージとしては、人 \(l+1\)、人 \(l+2\)、\(\cdots\)、人 \(r-1\) の中で一番最初に配置する人を決め打って行くような形です。

• \(\text{num}[l][r] = \sum_{i=l+1}^{r-1} (\text{num}[l][i] \times \text{num}[i][r] \times c1 \times \binom{r-l-2}{i-l-1})\)
• \(\text{cost}[l][r] = \sum_{i=l+1}^{r-1} ((\text{num}[l][i] \times \text{num}[i][r] \times c2+\text{num}[l][i] \times \text{cost}[i][r] \times c1+\text{cost}[l][i] \times \text{num}[i][r] \times c1) \times \binom{r-l-2}{i-l-1})\)

ここで、\(c1\) は「\(S_l\) が R である」と「\(S_r\) が L である」のうち真であるものの個数であり、また \(c2\) は \(S_l\) が R であるならば \(i-l\) を加算し、\(S_r\) が L であるならば \(r-i\) を加算したものの合計です。

計算量は \(O(N^3)\) となります。

実装例 (Python)

MAX = int(1e5)
MOD = 998244353
fac = [0]*MAX
finv = [0]*MAX
inv = [0]*MAX
fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1
for i in range(2,MAX):
    fac[i] = fac[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD
def binom(n,k):
    if n<0 or k<0 or n<k:
        return 0
    return fac[n]*finv[k]%MOD*finv[n-k]%MOD

N = int(input())
S = input()
num = [[0]*(N) for _ in range(N)]
cost = [[0]*(N) for _ in range(N)]
for i in range(N):
    num[i][(i+1)%N] = 1
for d in range(1,N+1):
    for l in range(N):
        r = (l+d)%N
        i = (l+1)%N
        while i != r:
            c1 = 0
            if S[l] == 'R': c1 += 1
            if S[r] == 'L': c1 += 1
            c2 = 0
            if S[l] == 'R': c2 += (i-l)%N
            if S[r] == 'L': c2 += (r-i)%N
            num[l][r] += num[l][i]*num[i][r]%MOD*c1%MOD*binom((r-l-2)%N,(i-l-1)%N)%MOD
            cost[l][r] += (num[l][i]*num[i][r]%MOD*c2%MOD+num[l][i]*cost[i][r]%MOD*c1%MOD+cost[l][i]*num[i][r]%MOD*c1%MOD)*binom((r-l-2)%N,(i-l-1)%N)%MOD
            num[l][r] %= MOD
            cost[l][r] %= MOD
            i = (i+1)%N
ans = 0
for i in range(N):
    ans += cost[i][i]
    ans %= MOD
ans *= finv[N]
ans %= MOD
print(ans)