M. Binary String Counting 2026
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Yes, this is yet another problem about counting binary strings.

You are given a string $$$s$$$ consisting of $$$n$$$ characters; each character is either 1 or 0. Also, you are given an integer $$$k$$$.

You can perform up to $$$k$$$ (possibly zero) operations on string $$$s$$$. Each operation has to be of one of three types:

  1. choose an index $$$i$$$ from $$$1$$$ to $$$n$$$ and replace $$$s_i$$$ with its inverse (that is, if $$$s_i$$$ is 1, replace it with 0, and vice versa);
  2. sort the characters of the string $$$s$$$ in non-descending order (assuming that 1 is greater than 0);
  3. sort the characters of the string $$$s$$$ in non-ascending order (also assuming that 1 is greater than 0).

String $$$t$$$ is reachable if it is possible to obtain it from $$$s$$$ by applying no more than $$$k$$$ operations. You have to calculate the number of reachable strings $$$t$$$.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 150$$$; $$$0 \le k \le n$$$).

The second line contains $$$s$$$ — a string consisting of exactly $$$n$$$ characters. Each character is either 1 or 0.

Output

Print one integer — the number of reachable strings. Since the answer can be huge, print it modulo $$$998244353$$$.

Examples
Input
7 1
0001000
Output
10
Input
5 2
10110
Output
22
Input
7 0
0101010
Output
1
Input
7 1
0000000
Output
8
Input
30 30
000000000000000000000000000000
Output
75497471
Note

In the first example, the following strings are reachable: 0001000, 1001000, 0101000, 0011000, 0000000, 0001100, 0001010, 0001001, 1000000, 0000001.