有 $n$ 位应聘者，可以按任意排列依次安排在 $n$ 天中。第 $i$ 天的题目由 $s_i$ 决定：$s_i=1$ 时，当天参加者会被录取；$s_i=0$ 时会被拒绝。

若某位应聘者到来前，之前未被录取的人数（被拒绝与主动放弃都计入）已达到其耐心值 $c$，则该应聘者直接放弃，不论当天题目为何。每天都会消耗一位应聘者的名额，放弃也会使未录用人数增加。

求最终至少录用 $m$ 人的应聘者编号排列数量，并对 $998244353$ 取模。即使耐心值相同，不同编号的应聘者仍然可区分。

输入格式

第一行包含两个整数 $n,m$。

第二行给出一个长度为 $n$ 的 $01$ 串 $s$。第三行包含 $n$ 个耐心值 $c_1,c_2,\dots,c_n$。

输出格式

输出符合条件的排列数对 $998244353$ 取模后的结果。

样例 1

3 2
101
1 1 2

2

样例 2

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

2204128

数据范围与原题特殊限制

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

• $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$。

测试点编号	$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$。

来源与数据说明

原题页面。以上题意为重新整理的表述，规则、输入输出和约束与原题一致。本题使用独立生成的训练数据，原题测试点表仅说明原比赛范围与特殊性质，本包评分不复刻官方测试点分布。标准输入输出，不要求文件读写。