AT_utpc2023_p Priority Queue 3

$ N $ 個の `+` と $ M $ 個の `-` からなる長さ $ N+M $ の文字列 $ S $ 、および $ M $ 個の整数からなる集合 $ A=\lbrace A_1,A_2,\dots,A_M\rbrace $ が与えられます。 集合 $ X=\lbrace \rbrace,Y=\lbrace \rbrace $ を用意し、 $ i=1,2,\dots,N+M $ の順に以下を行うことを考えます。 - $ S $ の $ i $ 文字目が `+` のとき、 $ 1 $ から $ N $ までの整数のうち、 $ X,Y $ のいずれにも含まれない整数を $ 1 $ つ選び、 $ X $ に追加する。 - $ S $ の $ i $ 文字目が `-` のとき、 $ X $ に含まれる整数の最小値 $ m $ を $ X $ から削除し、 $ m $ を $ Y $ に追加する。制約から、操作の直前に $ X $ は空でないことが保証される。 一連の操作で $ X $ に追加する整数の順番は $ N! $ 通り考えられますが、そのうち一連の操作を終えた後に $ Y=A $ となっているような順番の数を $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ S $ $ A_1 $ $ A_2 $ $ \dots $ $ A_M $

答えを $ 1 $ 行に出力せよ。

### Sample Explanation 1 条件を満たす一連の操作の例として以下のようなものが考えられます。 - $ i=1 $ のとき、 $ X $ に $ 3 $ を追加する。 $ X=\lbrace 3\rbrace,Y=\lbrace \rbrace $ となる。 - $ i=2 $ のとき、 $ X $ に $ 4 $ を追加する。 $ X=\lbrace 3,4\rbrace,Y=\lbrace \rbrace $ となる。 - $ i=3 $ のとき、 $ X $ に含まれる整数の最小値 $ 3 $ を $ X $ から削除して $ Y $ に追加する。 $ X=\lbrace 4\rbrace,Y=\lbrace 3\rbrace $ となる。 - $ i=4 $ のとき、 $ X $ に $ 2 $ を追加する。 $ X=\lbrace 2,4\rbrace,Y=\lbrace 3\rbrace $ となる。 - $ i=5 $ のとき、 $ X $ に $ 1 $ を追加する。 $ X=\lbrace 1,2,4\rbrace,Y=\lbrace 3\rbrace $ となる。 - $ i=6 $ のとき、 $ X $ に含まれる整数の最小値 $ 1 $ を $ X $ から削除して $ Y $ に追加する。 $ X=\lbrace 2,4\rbrace,Y=\lbrace 1,3\rbrace $ となる。 ### Sample Explanation 2 $ S $ の末尾は `-` とは限りません。 ### Constraints - 入力される数値は全て整数 - $ 1 \leq M \leq N \leq 300 $ - $ S $ は $ N $ 個の `+` と $ M $ 個の `-` からなる長さ $ N+M $ の文字列 - $ i=1,2,\dots,N+M $ に対し、 $ S $ の $ i $ 文字目までに登場する `-` の数は $ i $ 文字目までに登場する `+` の数を超えない - $ 1 \leq A_1 < A_2 < \dots < A_M \leq N $