Xiao Z and Xiao H want to start a company together, and there are $n$ applicants, numbered $1 \sim n$. Xiao Z and Xiao H hope to hire at least $m$ people.

Xiao H is the interviewer and will interview one person each day for the next $n$ days. Xiao Z is responsible for deciding the order in which the applicants come for an interview. Specifically, Xiao Z can choose a permutation $p$ of $1 \sim n$, and then notify the person numbered $p_i$ to come for an interview on the $i$-th day ($1 \le i \le n$).

Xiao H has prepared $n$ sets of interview questions with varying difficulty. Since the $n$ applicants have roughly the same skill level, their performance on the same set of questions is consistent. Specifically, the difficulty of the interview questions on the $i$-th day ($1 \le i \le n$) is $s_i \in \{0, 1\}$, where $s_i = 0$ means the difficulty of this set is high and no one can solve it; $s_i = 1$ means the difficulty of this set is low and everyone can solve it. Xiao H will decide whether to hire the applicant based on their performance: if the applicant does not solve the interview questions, they will be rejected; otherwise, they will be hired.

However, everyone has a certain limit on their patience. If too many people have not been hired before their interview, they will give up on participating in the interview. Specifically, the patience limit of the person numbered $i$ ($1 \le i \le n$) can be described by a non-negative integer $c_i$. If at least $c_i$ people have already been rejected or have given up on participating in the interview before them, they will also give up on participating in the interview.

Xiao Z wants to know how many interview sequences $p$ allow them to hire at least $m$ people. You need to help Xiao Z find the number of permutations $p$ that allow hiring at least $m$ people. Since the answer may be large, you only need to output the result modulo $998,244,353$.

Input

The first line contains two positive integers $n$ and $m$, representing the number of applicants and the number of people they hope to hire, respectively.

The second line contains a string of length $n$, $s_1 \dots s_n$, representing the difficulty of the interview questions for each day.

The third line contains $n$ non-negative integers $c_1, c_2, \dots, c_n$, representing the patience limit of each person.

Output

Output a single non-negative integer representing the number of permutations $p$ that allow hiring at least $m$ people, modulo $998,244,353$.

Examples

Input 1

3 2
101
1 1 2

Output 1

2

Note

There are 2 interview sequences $p$ that allow Xiao Z and Xiao H to hire at least 2 people: 1. $p = [1, 2, 3]$, hiring the person numbered 1 and the person numbered 3 in order; 2. $p = [2, 1, 3]$, hiring the person numbered 2 and the person numbered 3 in order.

Input 2

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

Output 2

2204128

Input 3

(See employ/employ3.in)

Output 3

(See employ/employ3.ans)

Note

This example satisfies the constraints for test cases $6 \sim 8$.

Input 4

(See employ/employ4.in)

Output 4

(See employ/employ4.ans)

Note

This example satisfies the constraints for test cases $12 \sim 14$.

Input 5

(See employ/employ5.in)

Output 5

(See employ/employ5.ans)

Note

This example satisfies the constraints for test cases $18 \sim 21$.

Constraints

For all test data, it is guaranteed that: $1 \le m \le n \le 500$; For all $1 \le i \le n$, $s_i \in \{0, 1\}$; * For all $1 \le i \le n$, $0 \le c_i \le n$.

Special Property A: For all $1 \le i \le n$, $s_i = 1$. Special Property B: There are at most 18 values of 1 in $s_1, s_2, \dots, s_n$, i.e., $\sum_{i=1}^n s_i \le 18$.