题目背景

由于评测机性能差异，本题时限提升 1 秒。

且似乎没有正解能拿到分

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

由于评测机性能差异，本题不要提交

提交了也是零分

题目描述

小 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$ 取模后的结果。

输入格式

输入的第一行包含两个正整数 $n, m$，分别表示前来应聘的人数和希望录用的人数。

输入的第二行包含一个长度为 $n$ 的字符串 $s_1 \dots s_n$，表示每一天的面试题的难度。

输入的第三行包含 $n$ 个非负整数 $c_1, c_2, \dots, c_n$，表示每个人的耐心上限。

输出格式

输出一行一个非负整数，表示能够录用至少 $m$ 人的排列 $p$ 的数量对 $998\,244\,353$ 取模后的结果。

输入输出样例 #1

输入 #1

3 2
101
1 1 2

输出 #1

2

输入输出样例 #2

输入 #2

10 5
1101111011
6 0 4 2 1 2 5 4 3 3

输出 #2

2204128

说明/提示

【样例 1 解释】

共有以下 2 种面试的顺序 $p$ 能够让小 Z 和小 H 录用至少 2 人:

1. $p = [1,2,3]$, 依次录用编号为 1 的人和编号为 3 的人;
2. $p = [2,1,3]$, 依次录用编号为 2 的人和编号为 3 的人。

【样例 3】

见选手目录下的 $\textbf{\textit{employ/employ3.in}}$ 与 $\textbf{\textit{employ/employ3.ans}}$。

该样例满足测试点 6 ~ 8 的约束条件。

【样例 4】

见选手目录下的 $\textbf{\textit{employ/employ4.in}}$ 与 $\textbf{\textit{employ/employ4.ans}}$。

该样例满足测试点 12 ~ 14 的约束条件。

【样例 5】

见选手目录下的 $\textbf{\textit{employ/employ5.in}}$ 与 $\textbf{\textit{employ/employ5.ans}}$。

该样例满足测试点 18 ~ 21 的约束条件。

【数据范围】

对于所有测试数据，保证:

• $1 \leq m \leq n \leq 500$;
• 对于所有 $1 \leq i \leq n$，均有 $s_i \in \{0,1\}$;
• 对于所有 $1 \leq i \leq n$，均有 $0 \leq c_i \leq n$。

::cute-table{tuack}

测试点编号	$n \leq$	$m$	特殊性质
$1,2$	$10$	$\leq n$	无
$3 \sim 5$	$18$	^	^
$6 \sim 8$	$10^2$		A
$9 \sim 11$	^		无
$12 \sim 14$	$500$	$=1$	^
$15$	^	$=n$
$16,17$		$\leq n$	A
$18 \sim 21$		^	B
$22 \sim 25$			无

特殊性质 A: 对于所有 $1 \leq i \leq n$，均有 $s_i = 1$。

特殊性质 B: 在 $s_1, s_2, \dots, s_n$ 中最多只有 18 个取值为 1，即 $\sum_{i=1}^{n} s_i \leq 18$。