まず、順列 \(P\) は必ず \((1)\) と \((1,2,\ldots,N)\) の並び替えを連続部分列として含むので \(S_1=\) x または \(S_N=\) x の場合答えは \(0\) です。以降は \(S_1=S_N=\) o の場合を考えます。

\(d_n\) を \(S\) が oxxx...xxo という形の長さ \(n\) の文字列であった場合の答えとします。

\(S_i=\) o となる \(i\) の集合を \(1=A_1 < A_2< \ldots <A_M = N\) とします。

\(P=()\) とし、\(i=1,2,\ldots,N\) の順に \(P\) の好きな場所に要素 \(i\) を挿入して \(P\) を作ることを考えると、求める答えは \(\displaystyle \prod_{i=1}^{M-1}d_{A_{i+1}-A_i+1}\) となります。したがって、 \(d_2,d_3,\ldots,d_N\) の値が求まれば良いです。

\((1,2,\ldots,N)\) の順列 \(P\) は \(N!\) 個ありますが、それらを \((1,2,\ldots,k)\) の並び替えを連続部分列として含むような \(k\geq 2\) の最小値で分類します。

最小値が \(k\) であるような \(P\) は、\((1,2,\ldots,k)\) の並び替えが \(d_k\) 通り、それ以外の要素の並び替えが \((N-k+1)!\) 通りです。したがって、\(\displaystyle N!=\sum_{k=2}^N d_k(N-k+1)!\) が成り立ちます。この漸化式を用いることで \(d_2,d_3,\ldots,d_N\) の値を計算量 \(O(N^2)\) で求めることができます。

また、形式的冪級数を用いることで \(O(N\log N)\) 時間に改善することもできます。

実装例(Python3)

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)