E. Binary String Woweetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputMouf is bored with themes, so he decided not to use any themes for this problem.You are given a binary$$$^{\text{∗}}$$$ string $$$s$$$ of length $$$n$$$. You are to perform the following operation exactly $$$k$$$ times: select an index $$$i$$$ ($$$1 \le i \le n$$$) such that $$$s_i = \mathtt{0}$$$; then flip$$$^{\text{†}}$$$ each $$$s_j$$$ for all indices $$$j$$$ ($$$1 \le j \le i$$$). You need to count the number of possible ways to perform all $$$k$$$ operations. Since the answer could be ginormous, print it modulo $$$998\,244\,353$$$.Two sequences of operations are considered different if they differ in the index selected at any step.$$$^{\text{∗}}$$$A binary string is a string that consists only of the characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.$$$^{\text{†}}$$$Flipping a binary character is changing it from $$$\mathtt{0}$$$ to $$$\mathtt{1}$$$ or vice versa.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows. The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 500$$$) — the length of the binary string $$$s$$$ and the number of times the operation must be performed, respectively.The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$ consisting of only characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.It is guaranteed that the sum of $$$n$$$ does not exceed $$$500$$$ over all test cases.OutputFor each test case, output a single integer — the number of ways you can perform exactly $$$k$$$ operations, modulo $$$998\,244\,353$$$.ExampleInput53 10103 20005 4010018 81100110020 2010010110101101010110Output2
3
10
27286
915530405
NoteIn the first test case, here are all the possible sequences of operations: $$$\mathtt{\color{red}{0}10} \xrightarrow{i = 1} \mathtt{110}$$$ $$$\mathtt{\color{red}{010}} \xrightarrow{i = 3} \mathtt{101}$$$ In the second test case, here are all the possible sequences of operations: $$$\mathtt{\color{red}{0}00} \xrightarrow{i = 1} \mathtt{\color{red}{1}00} \xrightarrow{i = 2} \mathtt{010}$$$ $$$\mathtt{\color{red}{0}00} \xrightarrow{i = 1} \mathtt{\color{red}{1}00} \xrightarrow{i = 3} \mathtt{011}$$$ $$$\mathtt{\color{red}{00}0} \xrightarrow{i = 2} \mathtt{\color{red}{11}0} \xrightarrow{i = 3} \mathtt{001}$$$