小 Z 和小 H 想要合伙开一家公司，共有 n 人前来应聘，编号为 1∼n。小 Z 和小 H 希望录用至少 m 人。
小 H 是面试官，将在接下来 n 天每天面试一个人。小 Z 负责决定应聘人前来面试的顺序。具体地，小 Z 可以选择一个 1∼n 的排列 p，然后在第 i (1≤i≤n) 天通知编号为 pi 的人前来面试。
小 H 准备了 n 套难度不一的面试题。由于 n 个前来应聘的人水平大致相同，因此对于同一套题，所有人的作答结果是一致的。具体地，第 i (1≤i≤n) 天的面试题的难度为 si∈{0,1}，其中 si=0 表示这套题的难度较高，没有人能够做出；si=1 表示这套题的难度较低，所有人都能做出。小 H 会根据面试者的作答结果决定是否录用，即如果面试者没有做出面试题，则会拒绝，否则会录用。
然而，每个人的耐心都有一定的上限，如果在他面试之前未录用的人数过多，则他会直接放弃参加面试。具体地，编号为 i (1≤i≤n) 的人的耐心上限可以用非负整数 ci 描述，若在他之前已经有不少于 ci 人被拒绝或放弃参加面试，则他也将放弃参加面试。
小 Z 想知道一共有多少种面试的顺序 p 能够让他们录用至少 m 人。你需要帮助小 Z 求出，能够录用至少 m 人的排列 p 的数量。由于答案可能较大，你只需要求出答案对 998244353 取模后的结果。
输入的第一行包含两个正整数 n,m，分别表示前来应聘的人数和希望录用的人数。
输入的第二行包含一个长度为 n 的字符串 s1…sn，表示每一天的面试题的难度。
输入的第三行包含 n 个非负整数 c1,c2,…,cn，表示每个人的耐心上限。
输出一行一个非负整数，表示能够录用至少 m 人的排列 p 的数量对 998244353 取模后的结果。
3 2 101 1 1 2
2
10 5 1101111011 6 0 4 2 1 2 5 4 3 3
2204128
共有以下 2 种面试的顺序 p 能够让小 Z 和小 H 录用至少 2 人:
对于所有测试数据，保证:
| 测试点编号 | n≤ | m | 特殊性质 |
|---|---|---|---|
| 1,2 | 10 | ≤n | 无 |
| 3∼5 | 18 | ^ | ^ |
| 6∼8 | 102 | ^ | A |
| 9∼11 | ^ | ^ | 无 |
| 12∼14 | 500 | =1 | ^ |
| 15 | ^ | =n | ^ |
| 16,17 | ^ | ≤n | A |
| 18∼21 | ^ | ^ | B |
| 22∼25 | ^ | ^ | 无 |
特殊性质 A: 对于所有 1≤i≤n，均有 si=1。
特殊性质 B: 在 s1,s2,…,sn 中最多只有 18 个取值为 1，即 ∑i=1nsi≤18。
