当前没有测试数据。

本题暂未上传测试数据，目前仅供阅读与练习。

本站练习请使用标准输入/输出；原卷中的文件名仅作原始资料参考。

题目描述

共有 $n$ 人前来应聘，编号为 $1\sim n$，公司希望录用至少 $m$ 人。小 Z 可以决定一个排列 $p$，在第 $i$ 天通知编号为 $p_i$ 的人参加面试。

第 $i$ 天面试题的难度用 $s_i\in\{0,1\}$ 表示：$s_i=0$ 表示没有人能做出，因此会被拒绝；$s_i=1$ 表示所有人都能做出，因此会被录用。

第 $i$ 个人的耐心上限为 $c_i$。若在他之前已经有不少于 $c_i$ 人被拒绝或放弃面试，则他将直接放弃面试。放弃面试的人也计入之后人员判断耐心时的总人数。

求能够使公司录用至少 $m$ 人的排列 $p$ 的数量，答案对 $998244353$ 取模。

输入格式

第一行两个正整数 $n,m$。第二行一个长度为 $n$ 的 $0/1$ 字符串 $s$。第三行 $n$ 个非负整数 $c_1,\ldots,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\le m\le n\le500$；$s_i\in\{0,1\}$；$0\le c_i\le n$。

原卷完整题面

以下保留原卷的图示、完整样例解释、分档约束和特殊性质，便于核对。原卷中引用的外部样例文件未随本次题面上传。

下载原卷题面 PDF