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:
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$$$.
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.
Print one integer — the number of reachable strings. Since the answer can be huge, print it modulo $$$998244353$$$.
7 10001000
10
5 210110
22
7 00101010
1
7 10000000
8
30 30000000000000000000000000000000
75497471
In the first example, the following strings are reachable: 0001000, 1001000, 0101000, 0011000, 0000000, 0001100, 0001010, 0001001, 1000000, 0000001.
| Name |
|---|


