G - Restricted Permutation 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 550 点

問題文

整数 N と o と x からなる長さ N の文字列 S が与えられます。

以下の条件を満たす (1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) の個数を 998244353 で割ったあまりを求めてください。

  • k=1,2,\ldots,N に対し、以下の 2 つは同値となる。
    • S_k= o
    • P が (1,2,\ldots,k) の順列を連続部分列として含む

制約

  • 1\le N\le 2000
  • S_i は o と x からなる長さ N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを出力せよ。

入力例 1

3
oxo

出力例 1

2

P=(1,3,2),(2,3,1) が条件を満たします。

入力例 2

7
xxxxxxx

出力例 2

0

条件を満たす P は存在しません。

入力例 3

15
oxxxoxxxxxooxxo

出力例 3

1627648

Score : 550 points

Problem Statement

You are given an integer N and a string S of length N consisting of o and x.

Find the number, modulo 998244353, of permutations P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) satisfying the following condition.

  • For k=1,2,\ldots,N, the following two are equivalent.
    • S_k= o
    • P contains a permutation of (1,2,\ldots,k) as a contiguous subsequence.

Constraints

  • 1\le N\le 2000
  • S_i is a string of length N consisting of o and x.

Input

The input is given from Standard Input in the following format:

N
S

Output

Output the answer.

Sample Input 1

3
oxo

Sample Output 1

2

P=(1,3,2),(2,3,1) satisfy the condition.

Sample Input 2

7
xxxxxxx

Sample Output 2

0

There is no P satisfying the condition.

Sample Input 3

15
oxxxoxxxxxooxxo

Sample Output 3

1627648