upd：感谢 Jorisy 指出一处 typo，已修复。

【题意】

小 Z 和小 H 想要合伙开一家公司，共有 $n$ 人前来应聘，编号为 $1 \sim n$。小 Z 和小 H 希望录用至少 $m$ 人。

小 H 是面试官，将在接下来 $n$ 天每天面试一个人。小 Z 负责决定应聘人前来面试的顺序。具体地，小 Z 可以选择一个 $1 \sim n$ 的排列 $p$，然后在第 $i$ ($1 \leq i \leq n$) 天通知编号为 $p_i$ 的人前来面试。

小 H 准备了 $n$ 套难度不一的面试题。由于 $n$ 个前来应聘的人水平大致相同，因此对于同一套题，所有人的作答结果是一致的。具体地，第 $i$ ($1 \leq i \leq n$) 天的面试题的难度为 $s_i \in \{0,1\}$，其中 $s_i = 0$ 表示这套题的难度较高，没有人能够做出；$s_i = 1$ 表示这套题的难度较低，所有人都能做出。小 H 会根据面试者的作答结果决定是否录用，即如果面试者没有做出面试题，则会拒绝，否则会录用。

然而，每个人的耐心都有一定的上限，如果在他面试之前未录用的人数过多，则他会直接放弃参加面试。具体地，编号为 $i$ ($1 \leq i \leq n$) 的人的耐心上限可以用非负整数 $c_i$ 描述，若在他之前已经有不少于 $c_i$ 人被拒绝或放弃参加面试，则他也将放弃参加面试。

小 Z 想知道一共有多少种面试的顺序 $p$ 能够让他们录用至少 $m$ 人。你需要帮助小 Z 求出，能够录用至少 $m$ 人的排列 $p$ 的数量。由于答案可能较大，你只需要求出答案对 $998\,244\,353$ 取模后的结果。

$1 \leq m \leq n \leq 500$.

【题解】

哎。这个t4不是比【最古的遗迹】还简单的同类题？？？那我场上不做这个T4一直调那个弱智T3不是纯糖？？？

把计数排列看作天和人的匹配。按值域考虑每个人和哪个匹配。大致为 $dp(i,j)$ 表示 $c\le i$ 的人里有 $j$ 个面试失败的方案数。

然后就发现当决策一个人面试失败的时候并不只涉及 $c$ 比它小的人，因为可以让一个 $c$ 大的人遇到 $0$，所以还要额外记录后面有多少个人面试失败了。

为了避免记录每个人的状态，我们要考虑什么情况下两个不同的人就本质相同了。

把 $(i,c_{p_i})$ 在坐标系上画成柱状图，画一条左下到右上的折线表示每一天的失败人数变化。这样就容易看出因为折线是单调向上的，所以在某次折线达到 $x$ 的高度后，之后耐心值 $\le x$ 的人都不可能被录取，而 $>x$ 的人只要放在 $1$ 的位置就一定会被录取。

所以考虑把人分作耐心值 $\le x,>x$ 考虑。因为 $x$ 是单调上升的，所以过程中会有一些 $>x$ 的人进入 $\le x$，但是 $\le x$ 的永远会 $\le x$。所以 "$\le x$ 的人" 是确定的部分，"$>x$ 的人" 是不确定的部分。用【P7213 最古の遺跡 3】的经典延迟确定的 trick，考虑设 $dp(i,j,k)$ 表示决策前 $i$ 天的安排、有 $j$ 个人失败、有 $k$ 个位置的人耐心值 $>j$（等待后面决策），在 $dp$ 里只决策前 $i$ 天耐心值 $\le j$ 的方案数。

使用刷表法转移。考虑第 $i+1$ 天的人是要失败还是要通过。记 $cnt_i$ 表示耐心值为 $i$ 的人数，$sc$ 为 $cnt$ 的前缀和。

• $s_{i+1}=0$。

  必须失败。分类讨论 $c_{p_{i+1}}$ 与 $j+1$ 的大小关系，并把 $k$ 个人里 $=j+1$ 的纳入考虑。

  • $c_{p_{i+1}}>j+1$。

    $$\sum_{w=0}^k\binom{k}{w}\binom{cnt_{j+1}}{w}w!dp(i,j,k)\rightarrow dp(i+1,j+1,k-w+1)$$

  • $c_{p_{i+1}}\le j+1$。

    $$\sum_{w=0}^k\binom{k}{w}\binom{cnt_{j+1}}{w}w!(sc_{j+1}-(i-(k-w))dp(i,j,k)\rightarrow dp(i+1,j+1,k-w)$$

• $s_{i+1}=1$。

  • $c_{p_{i+1}}>j$，此时会录取，$j$ 不变。

    $$dp(i,j,k)\rightarrow dp(i+1,j,k+1)$$

  • $c_{p_{i+1}}\le j$，此时会放弃，$j$ 加一。

    $$\sum_{w=0}^k\binom{k}{w}\binom{cnt_{j+1}}{w}w!(sc_{j}-(i-k))dp(i,j,k)\rightarrow dp(i+1,j+1,k-w)$$

虽然看起来要枚举 $w$ 是 $O(n^4)$ 的，但因为总人数 $O(n)$，所以 $w$ 一共只能枚举 $n$ 次。故总复杂度是 $O(n^3)$ 的。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 505, mod = 998244353;

void add(ll &x, ll y) {
	x += y;
	if (x >= mod)
		x -= mod;
}

int n, m;
int s[N];

ll fpow(ll a, ll b = mod - 2, ll p = mod) {
	ll mul = 1;
	while (b) {
		if (b & 1)
			mul = mul * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return mul;
}
ll fac[N], ifac[N];

ll C(ll n, ll m) {
	return m < 0 || m > n ? 0 : fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

ll dp[N][N][N] = {{{}}};

int cnt[N], sc[N];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		scanf("%1d", &s[i]);
	for (int i = 1, x; i <= n; i++) {
		cin >> x;
		cnt[x]++;
	}
	sc[0] = cnt[0];
	for (int i = 1; i <= n; i++)
		sc[i] = sc[i - 1] + cnt[i];
	
	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = fac[i - 1] * i % mod;
	ifac[n] = fpow(fac[n]);
	for (int i = n - 1; i >= 0; i--)
		ifac[i] = ifac[i + 1] * (i + 1) % mod;
	
	dp[0][0][0] = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= i; j++)
			for (int k = 0; k <= i; k++)
				if (dp[i][j][k]) {
					if (s[i + 1] == 0) {
						for (int w = 0; w <= k && w <= cnt[j + 1]; w++)
							add(dp[i + 1][j + 1][k - w + 1], 
								C(cnt[j + 1], w) * fac[w] % mod * C(k, w) % mod * dp[i][j][k] % mod);
						for (int w = 0; w <= k && w <= cnt[j + 1]; w++)
							add(dp[i + 1][j + 1][k - w],
								C(cnt[j + 1], w) * fac[w] % mod * C(k, w) % mod * (sc[j + 1] - (i - (k - w))) % mod * dp[i][j][k] % mod);
					}
					else {
						for (int w = 0; w <= k && w <= cnt[j + 1]; w++)
							add(dp[i + 1][j + 1][k - w],
								C(cnt[j + 1], w) * fac[w] % mod * C(k, w) % mod * (sc[j] - (i - k)) % mod * dp[i][j][k] % mod);
						add(dp[i + 1][j][k + 1], dp[i][j][k]);
					}
				}
	
	ll ans = 0;
	for (int j = 0; j <= n - m; j++)
		add(ans, dp[n][j][n - sc[j]] * fac[n - sc[j]] % mod);
	cout << ans << '\n';
	return 0;
}