← 返回题目列表

Codeforces · 2109/E

E. 二进制字符串 Wowee

中文机器翻译题面 查看原题

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$$$ 为模。

示例

输入
复制

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

输出
复制

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