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$ 的整数，加入集合 $X$。 - 当 $S$ 的第 $i$ 个字符为 `-` 时，从 $X$ 中取出最小的整数 $m$，将其自 $X$ 中删除，并加入 $Y$。根据约束条件，进行该操作前 $X$ 一定非空。 对于 $X$ 中加入的整数的顺序总共有 $N!$ 种可能，其中有多少种顺序能使得一系列操作完成后 $Y=A$，请输出这个方案数对 $998244353$ 取模的结果。

输入通过标准输入按以下格式给出。 > $N$　$M$　$S$　$A_1$　$A_2$　$\dots$　$A_M$

请输出一个整数，表示满足条件的方案数对 $998244353$ 取模的值。

### 样例解释 1 满足条件的一系列操作之一如下： - 当 $i=1$ 时，将 $3$ 加入 $X$，此时 $X=\lbrace 3 \rbrace,\,Y=\lbrace \rbrace$。 - 当 $i=2$ 时，将 $4$ 加入 $X$，此时 $X=\lbrace 3,4 \rbrace,\,Y=\lbrace \rbrace$。 - 当 $i=3$ 时，从 $X$ 中取出最小的 $3$，从 $X$ 移到 $Y$。此时 $X=\lbrace 4 \rbrace,\,Y=\lbrace 3 \rbrace$。 - 当 $i=4$ 时，将 $2$ 加入 $X$，此时 $X=\lbrace 2,4 \rbrace,\,Y=\lbrace 3 \rbrace$。 - 当 $i=5$ 时，将 $1$ 加入 $X$，此时 $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$。 ### 样例解释 2 $S$ 的结尾不一定是 `-`。 ### 数据范围与约定 - 所有输入数据均为整数。 - $1 \leq M \leq N \leq 300$ - $S$ 是由 $N$ 个 `+` 和 $M$ 个 `-` 组成的、长度为 $N+M$ 的字符串。 - 对于 $i=1,2,\dots,N+M$，在前 $i$ 个字符中，`-` 的数量不超过 `+` 的数量。 - $1 \leq A_1 < A_2 < \dots < A_M \leq N$。 由 ChatGPT 5 翻译