CF2109E Binary String Wowee

Mouf 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.

Each 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.

For each test case, output a single integer — the number of ways you can perform exactly $ k $ operations, modulo $ 998\,244\,353 $ .

In 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} $