#P18152. Priority Queue 3

Priority Queue 3

Priority Queue 3

给定一个长度为 N+MN+M 的字符串 SS,其中恰有 NN 个 + 和 MM 个 -,以及一个由 MM 个整数组成的集合 A={A1,A2,…,AM}A=\{A_1,A_2,\dots,A_M\}。

准备两个集合 X=∅X=\varnothing、Y=∅Y=\varnothing,依次对 i=1,2,…,N+Mi=1,2,\dots,N+M 执行:

  • 若 SS 的第 ii 个字符是 +,从 11 到 NN 中选一个既不在 XX 也不在 YY 中的整数,加入 XX;
  • 若 SS 的第 ii 个字符是 -,从 XX 中取出最小的整数 mm,把它从 XX 删除并加入 YY。题面保证此时 XX 非空。

把整数加入 XX 的顺序共有 N!N! 种。求其中有多少种顺序,使得全部操作结束后 Y=AY=A。答案对 998244353998244353 取模。

输入格式

第一行两个整数 N,MN,M(1≤M≤N≤3001\le M\le N\le 300)。

第二行一个长度为 N+MN+M 的字符串 SS,由 + 和 - 组成;对任意前缀,- 的个数不超过 + 的个数。

第三行 MM 个整数 A1<A2<⋯<AMA_1<A_2<\dots<A_M(1≤Ai≤N1\le A_i\le N)。

输出格式

输出一个整数,表示满足条件的加入顺序数对 998244353998244353 取模的结果。

样例 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