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