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 翻译