题目描述

Mouf 厌倦了主题，所以他决定不使用任何主题来解决这个问题。

给你一个长度为 $n$ 的二进制 $^{\text{∗}}$ 字符串 $s$ 。您需要执行以下操作 $k$ 次：

• 选择一个索引 $i$ ( $1 \le i \le n$ )，使得 $s_i = \mathtt{0}$ ；
• 然后对所有索引 $j$ ( $1 \le j \le i$ ) 的每个 $s_j$ 进行翻转 $^{\text{†}}$ 。

您需要计算执行所有 $k$ 操作的可能方法的数量。

由于答案可能非常庞大，因此请打印出它的模数 $998\,244\,353$ 。

如果两个操作序列在任何一步所选的索引不同，则视为不同的操作序列。

$^{\text{∗}}$ 一个二进制字符串是指仅由字符 $\mathtt{0}$ 和 $\mathtt{1}$ 组成的字符串。

$^{\text{†}}$ 将二进制字符从 $\mathtt{0}$ 变为 $\mathtt{1}$ 或反之。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 100$ )。测试用例说明如下。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ （ $1 \le k \le n \le 500$ ）。( $1 \le k \le n \le 500$ ) - 分别是二进制字符串 $s$ 的长度和必须执行操作的次数。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$ ，该字符串仅由字符 $\mathtt{0}$ 和 $\mathtt{1}$ 组成。

保证所有测试用例中 $n$ 的总和不超过 $500$ 。

输出格式

对于每个测试用例，输出一个整数 - 您可以执行 $k$ 次操作的次数，模数为 $998\,244\,353$ 。

样例

5
3 1
010
3 2
000
5 4
01001
8 8
11001100
20 20
10010110101101010110

2
3
10
27286
915530405

提示

样例1解释

注

在第一个测试案例中，以下是所有可能的操作顺序：

• $\mathtt{\color{red}{0}10} \xrightarrow{i = 1} \mathtt{110}$
• $\mathtt{\color{red}{010}} \xrightarrow{i = 3} \mathtt{101}$

在第二个测试用例中，以下是所有可能的操作序列：

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