AT_abc468_g [ABC468G] Restricted Permutation

整数 $ 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) $ の順列を連続部分列として含む

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

答えを出力せよ。

### Sample Explanation 1 $ P=(1,3,2),(2,3,1) $ が条件を満たします。 ### Sample Explanation 2 条件を満たす $ P $ は存在しません。 ### Constraints - $ 1\le N\le 2000 $ - $ S_i $ は `o` と `x` からなる長さ $ N $ の文字列