Mouf 对主题感到厌倦,因此他决定不对这个问题使用任何主题。
给你一个二进制$$$^{\text{*}}$$$ 字符串$$$s$$$,长度为$$$n$$$。您将精确执行以下操作 $$$k$$$ 次:
- 选择索引 $$$i$$$ ($$$1 \le i \le n$$$) 使得 $$$s_i = \mathtt{0}$$$;
- 然后翻转 $$$^{\text{†}}$$$ 每个 $$$s_j$$$ 对于所有索引 $$$j$$$ ($$$1 \le j \le i$$$)。
您需要计算执行所有 $$$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$$$) - 分别是二进制字符串 $$$s$$$ 的长度和必须执行操作的次数。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,仅由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$500$$$。
输出
对于每个测试用例,输出一个整数 - 您可以精确执行 $$$k$$$ 运算的方式数,以 $$$998\,244\,353$$$ 为模。
示例
输入复制
53 10103 20005 4010018 81100110020 2010010110101101010110
输出复制
2 3 10 27286 915530405
注意
在第一个测试用例中,以下是所有可能的操作序列:
- $$$\mathtt{\color{red}{0}10} \xrightarrow{i = 1} \mathtt{110}$$$
- $$$\mathtt{\color{红色}{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}$$$