#P18152. Priority Queue 3
Priority Queue 3
Priority Queue 3
给定一个长度为 的字符串 ,其中恰有 个 + 和 个 -,以及一个由 个整数组成的集合 。
准备两个集合 、,依次对 执行:
- 若 的第 个字符是
+,从 到 中选一个既不在 也不在 中的整数,加入 ; - 若 的第 个字符是
-,从 中取出最小的整数 ,把它从 删除并加入 。题面保证此时 非空。
把整数加入 的顺序共有 种。求其中有多少种顺序,使得全部操作结束后 。答案对 取模。
输入格式
第一行两个整数 ()。
第二行一个长度为 的字符串 ,由 + 和 - 组成;对任意前缀,- 的个数不超过 + 的个数。
第三行 个整数 ()。
输出格式
输出一个整数,表示满足条件的加入顺序数对 取模的结果。
样例 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