题目描述

给定一个由 $n$ 个 + 和 $m$ 个 - 组成、长度为 $n+m$ 的字符串 $s$，以及一个由 $m$ 个整数组成的集合

准备两个集合 $X=\varnothing$、$Y=\varnothing$，并按照 $i=1,2,\ldots,n+m$ 的顺序依次执行以下操作：

• 当 $s$ 的第 $i$ 个字符为 + 时，从 $1$ 到 $n$ 的整数中选择一个既不在 $X$ 中、也不在 $Y$ 中的整数，将其加入集合 $X$。
• 当 $s$ 的第 $i$ 个字符为 - 时，从 $X$ 中取出最小的整数 $x$，将其从 $X$ 中删除并加入集合 $Y$。根据约束，执行该操作前 $X$ 一定非空。

对于向 $X$ 中加入整数的顺序，共有 $n!$ 种可能。求其中有多少种顺序能够使所有操作完成后满足

答案对 $998244353$ 取模。

输入格式

第一行包含两个整数 $n,m$。

第二行包含一个长度为 $n+m$ 的字符串 $s$。

第三行包含 $m$ 个整数 $a_1,a_2,\ldots,a_m$。

输出格式

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

样例 1

输入

4 2
++-++-
1 3

输出

4

样例 2

输入

6 4
++-++---++
2 3 4 6

输出

48

样例 3

输入

20 10
++++-++++++--+--+-+++++--+-++-
1 2 3 4 5 6 7 9 12 13

输出

179396825

样例 1 解释

满足条件的一组操作方案如下：

1. 当 $i=1$ 时，将 $3$ 加入 $X$，此时 $X=\{3\},Y=\varnothing$。
2. 当 $i=2$ 时，将 $4$ 加入 $X$，此时 $X=\{3,4\},Y=\varnothing$。
3. 当 $i=3$ 时，从 $X$ 中取出最小的 $3$，并将其从 $X$ 移入 $Y$。此时 $X=\{4\},Y=\{3\}$。
4. 当 $i=4$ 时，将 $2$ 加入 $X$，此时 $X=\{2,4\},Y=\{3\}$。
5. 当 $i=5$ 时，将 $1$ 加入 $X$，此时 $X=\{1,2,4\},Y=\{3\}$。
6. 当 $i=6$ 时，从 $X$ 中取出最小的 $1$，并将其从 $X$ 移入 $Y$。此时 $X=\{2,4\},Y=\{1,3\}$。

样例 2 解释

字符串 $s$ 的末尾不一定是 -。

数据范围

对于全部数据：

• $1\le m\le n\le 500$；
• $s$ 是一个由 $n$ 个 + 和 $m$ 个 - 组成、长度为 $n+m$ 的字符串；
• 对于任意 $i=1,2,\ldots,n+m$，在 $s$ 的前 $i$ 个字符中，- 的数量不超过 + 的数量；
• $1\le a_1<a_2<\cdots<a_m\le n$。

子任务