Let \((P_1,P_2,\ldots,P_{N-1},P_N)\) be the sequence of \(N\) people to be removed, where \(P_N\) denotes the person who will not be removed till the end. Then, obviously, \(P\) is a permutation of \((1,2,\ldots,N)\).

Consider inspecting \(P\) in the decreasing order. Then, this problem can be regarded as placing Person \(P_N\), Person \(P_{N-1}\), \(\cdots\), and Person \(P_1\), in this order, on an empty circle. Formally speaking, it can be expressed as follows.

You will place Person \(P_N\), Person \(P_{N-1}\), \(\cdots\), and Person \(P_1\), in this order, on an empty circle.

Every time a person is placed, the person should shout either “clockwise!” or “counterclockwise!”. If the former is shouted, the person next to the placed person in the clockwise direction should be facing in the counterclockwise direction, and vice versa. The distance from the placed person to that person is added to the cost.

Find the sum of the cost for all the possible ways to place (the contents of \(P\) + which word each person shouted), and output the sum divided by \(N!\) modulo \(998244353\).

Let \(\text{num}[l][r]\) be the number of ways to place Person \(l+1\), Person \(l+2\), \(\cdots\), and Person \(r-1\), starting from the state where Person \(l\) and Person \(r\) are already placed.

Similarly, let \(\text{cost}[l][r]\) be the sum of total cost incurred to place Person \(l+1\), Person \(l+2\), \(\cdots\), and Person \(r-1\), starting from the state where Person \(l\) and Person \(r\) are already placed.

Then, the transition will be as follows. The intuition is to divide into cases depending on which of Person \(l+1\), Person \(l+2\), \(\cdots\), or Person \(r-1\), to place first.

• \(\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})\)

Here, \(c1\) is the number of those which “\(S_l\) is R” and “\(S_r\) is L” is true, and \(c2\) is the sum of \(i-l\) if \(S_l\) is R and \(r-i\) if \(S_r\) is L.

The time complexity is \(O(N^3)\).

Sample code (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)