CF2109E.Binary String Wowee

Mouf 觉得主题太无聊了，所以他决定这道题不使用任何主题。

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

• 选择一个下标 $i$（$1 \le i \le n$）满足 $s_i = \mathtt{0}$；
• 然后翻转$^{\text{†}}$所有 $s_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$ 取模的结果。

第一个测试用例解释：
所有可能的操作序列如下：

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

第二个测试用例解释：
所有可能的操作序列如下：

1. $\mathtt{\color{red}{0}00} \xrightarrow{i = 1} \mathtt{\color{red}{1}00} \xrightarrow{i = 2} \mathtt{010}$
2. $\mathtt{\color{red}{0}00} \xrightarrow{i = 1} \mathtt{\color{red}{1}00} \xrightarrow{i = 3} \mathtt{011}$
3. $\mathtt{\color{red}{00}0} \xrightarrow{i = 2} \mathtt{\color{red}{11}0} \xrightarrow{i = 3} \mathtt{001}$

翻译由 DeepSeek V3 完成