First of all, the permutation \(P\) always contain permutations of \((1)\) and \((1,2,\ldots,N)\) as a subarray, so the answer is \(0\) if \(S_1=\) x or \(S_N=\) x. We now assume that \(S_1=S_N=\) o.

Let \(d_n\) be the answer when \(S\) is the length-\(n\) string of the form oxxx...xxo.

Let \(1=A_1 < A_2< \ldots <A_M = N\) be the set of indices \(i\) with \(S_i=\) o.

Starting from \(P=()\), consider constructing \(P\) by inserting the element \(i\) to any position for \(i=1,2,\ldots,N\). Then the answer is \(\displaystyle \prod_{i=1}^{M-1}d_{A_{i+1}-A_i+1}\). Therefore, it is sufficient to find the values of \(d_2,d_3,\ldots,d_N\).

There are \(N!\) permutations \(P\) of \((1,2,\ldots,N)\). We will classify them by the minimum \(k\geq 2\) such that \((1,2,\ldots,k)\) is contained as a subarray.

For the permutations \(P\) with the minimum value \(k\), there are \(d_k\) ways to rearrange \((1,2,\ldots,k)\), and \((N-k+1)!\) ways to rearrange the others. Therefore, \(\displaystyle N!=\sum_{k=2}^N d_k(N-k+1)!\). This recurrence relation allows us to find the values \(d_2,d_3,\ldots,d_N\) in \(O(N^2)\) time.

One can also utilize Formal Power Series (FPS) tricks to improve it to \(O(N\log N)\) time.

Sample code (Python 3)

n = int(input())
s = input()
MOD = 998244353
if s[0] == "x" or s[-1] == "x":
    print(0)
    exit()
fac = [1] * (n + 1)
for i in range(1, n + 1):
    fac[i] = fac[i - 1] * i % MOD
d = [0] * (n + 1)
d[1] = 1
for i in range(2, n + 1):
    d[i] = fac[i]
    for k in range(2, i):
        d[i] -= d[k] * fac[i - k + 1]
        d[i] %= MOD
ans = 1
for x in s.split("o")[1:-1]:
    ans *= d[len(x) + 2]
    ans %= MOD
print(ans)