考虑找一些关于合法的 \(X\) 加入的数的判定条件。
假设遇到了一个 \(\operatorname{pop}\) 操作，令这里删除的数为 \(a_i\)，显然 \(X\) 中的数应该要有 \(a_i\)，其次 \(X\) 中其他的加入的数要么 \(> a_i\) 要么是 \(a\) 中的元素（在前面的 \(\operatorname{pop}\) 就已经被删了）。
于是可以知道，令最大的一个还没有被 \(\operatorname{pop}\) 出去的 \(a\) 中元素为 \(a_j\)，\(X\) 中的元素要么 \(> a_j\) 要么是 \(a\) 中元素。
接下来就有个想法就是直接 DP。
考虑令 \(f_{i, j}\) 为前 \(i\) 个条件，最大的一个还没有被 \(\operatorname{pop}\) 出去的 \(a\) 中元素为 \(a_j\) 的方案数。
但是因为还有上文提到的，可能 \(X\) 加入的数之中还有 \(a\) 中的 \(a_k < a_j\)，不是很好处理了。
于是考虑再加一维 \(k\)。
\(f_{i, j, k}\) 表示前 \(i\) 个条件，最大的一个还没有被 \(\operatorname{pop}\) 出去的 \(a\) 中元素为 \(a_j\)，当前 \(X\) 中 \(a\) 的元素的个数有 \(k\) 个的方案数。
好像看着就差不多了。
但是考虑到 \(\operatorname{pop}\) 的时候，有可能在 \(k = 1\) 的时候 \(a\) 中 \(\operatorname{pop}\) 的数其实不是 \(a_j\)，即 \(a_j\) 没有在 \(X\) 中。
于是再加一维 \(0 / 1\)。
\(f_{i, j, k, 0 / 1}\) 表示前 \(i\) 个条件，最大的一个还没有被 \(\operatorname{pop}\) 出去的 \(a\) 中元素为 \(a_j\)，当前 \(X\) 中 \(a\) 的元素的个数有 \(k\) 个，\(a_j\) 是否在 \(X\) 中的方案数。
接下来考虑转移。
令前 \(i - 1\) 个操作有 \(x\) 个 \(\operatorname{push}\) 操作和 \(y\) 个 \(\operatorname{pop}\) 操作。
若第 \(i\) 个操作为 \(\operatorname{push}\)：
- \(\operatorname{push}\) 了一个不在 \(a\) 中的元素。
这个元素有 \(\operatorname{cnt} = (n - a_j) - (m - j) - (x - y - k)\) 个选择（\(n - a_j\) 为 \(> a_j\) 的数量，后面的为已经选了的 \(> a_j\) 的数量）。
那么当 \(\operatorname{cnt} > 0, x - y - k\ge 0\) 时，有 \(f_{i - 1, j, k, p}\times cnt \to f_{i, j, k, p}\)。 - \(\operatorname{push}\) 了一个 \(a\) 中的非 \(a_j\) 元素。
考虑把这个元素是什么的贡献推迟到后面再算，即现在在这个位置放一个“占位符”，后面再来填补这个地方。
\(f_{i - 1, j, k, p}\to f_{i - 1, j, k + 1, p}\)。 - \(\operatorname{push}\) 了 \(a_j\)。
那么 \(X\) 就相当于从没有 \(a_j\) 到了有 \(a_j\)。
\(f_{i - 1, j, k, 0}\to f_{i, j, k + 1, 1}\)。
若第 \(i\) 个操作为 \(\operatorname{pop}\)：
- \(\operatorname{pop}\) 的就为 \(a_j\)。
可以知道现在一定满足 \(k = 1, t = 1\)。
那么这个时候考虑钦定下一个 \(j'\)。
此时相当于有 \(j - j' - 1\) 个元素还不知道填在哪里，根据上面的转移，要把这些数放到“占位符”上，也就统计了“占位符”上具体是什么值的贡献。
占位符的数量很好算，即为 \(y - (m - j)\)（有 \(y\) 次 \(\operatorname{pop}\)，且前 \(m - j\) 个已经选好了）。
那么当 \(j - j' - 1\le cnt\) 时，有转移 \(f_{i - 1, j, 1, 1}\times \binom{cnt}{j - j' - 1}\times (j - j' - 1)!\to f_{i, j', 0, 0}\)。 - \(\operatorname{pop}\) 的不为 \(a_j\)。
还是一样的，不去在意是哪个元素。
当 \(k\ge 1\) 时（\(k\not = 1\lor p\not = 1\)），有转移 \(f_{i - 1, j, k, p}\to f_{i, j, k - 1, p}\)。
时间复杂度 \(\mathcal{O}((n + m)m^2)\)。
#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 998244353;
inline void add(ll &x, ll y) {(x += y) %= mod;}
inline ll qpow(ll a, ll b = mod - 2, ll v = 1) {
while (b) b & 1 && ((v *= a) %= mod), b >>= 1, (a *= a) %= mod;
return v;
}
const int maxn = 3e2 + 5;
ll f[maxn + maxn][maxn][maxn][2];
ll fac[maxn], ifac[maxn];
inline ll A(int n, int m) {return fac[n] * ifac[n - m] % mod;}
char S[maxn + maxn];
int a[maxn];
int main() {
int n, m;
scanf("%d%d%s", &n, &m, S + 1);
for (int i = 1; i <= m; i++)
scanf("%d", &a[i]);
for (int i = fac[0] = 1; i <= m; i++)
fac[i] = fac[i - 1] * i % mod;
ifac[m] = qpow(fac[m]);
for (int i = m; i; i--)
ifac[i - 1] = ifac[i] * i % mod;
f[0][m][0][0] = 1;
for (int i = 1, x = 0, y = 0; i <= n + m; i++) {
if (S[i] == '+') {
for (int j = 0; j <= m; j++)
for (int k = 0; k <= std::min(i, j); k++) {
for (int t : {0, 1}) {
int in = x - y - k;
int cnt = (n - a[j]) - (m - j) - in;
if (in >= 0 && cnt > 0)
add(f[i][j][k][t], f[i - 1][j][k][t] * cnt);
if (k)
add(f[i][j][k][t], f[i - 1][j][k - 1][t]);
}
if (k)
add(f[i][j][k][1], f[i - 1][j][k - 1][0]);
}
x++;
} else {
for (int j = 0; j <= m; j++)
for (int k = 1; k <= std::min(i, j); k++)
for (int t : {0, 1}) {
if (k == 1 && t == 1)
continue;
add(f[i][j][k - 1][t], f[i - 1][j][k][t]);
}
for (int j = 0; j <= m; j++) {
int cnt = y - (m - j);
for (int j_ = 0; j_ < j; j_++)
if (j - j_ - 1 <= cnt)
add(f[i][j_][0][0], f[i - 1][j][1][1] * A(cnt, j - j_ - 1));
}
y++;
}
}
printf("%lld\n", f[n + m][0][0][0]);
return 0;
}