← 返回题目列表

Codeforces · 2161/E

E. 左永远是右

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

考虑一个长度为 $$$n$$$ 和奇数 $$$k$$$ 的二进制字符串。我们将二进制字符串称为 好 如果对于长度为 $$$k$$$ 的每个子字符串,该子字符串最左边的字符出现的次数多于其他字符。

例如,如果 $$$k = 3$$$, 000101 是一个很好的字符串,因为对于长度为 3 的所有子字符串 (000, 001, 010,和 101) 子字符串的第一个字符比其他字符出现的次数多。另一方面, 1011 不好,因为该属性是 false 011.

给定一个由字符组成的长度 $$$n$$$ 的模式 0, 1 和 ?,找出将问号替换为的方法的数量 0 or 1,这样生成的二进制字符串就很好。由于答案可能很大,请对 $$$998\,244\,353$$$ 求模。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$3 \le k \le n \le 10^5$$$,$$$k$$$ 是奇数)。第二行包含 $$$n$$$ 字符 0, 1 or ? — 模式。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印替换方法的数量 ? 与 0 or 1 这样得到的字符串是好的,模$$$998\,244\,353$$$。

示例

输入
复制

3
5 3
0??0?
7 7
1??1??1
9 5
?????????

输出
复制

3
15
46

注意

在第一个示例中,使模式良好的三种有效方法是 00000, 00001,和 00101。在第二个示例中,唯一无效的方式(总共 16 种方式中)是 1001001.