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.

Input

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.

Output

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

Note

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

Binary String Wowee

Examples