CF2161E.Left is Always Right

Consider a binary string of length $n$ and an odd number $k$. We will call the binary string good if for each substring of length $k$, the leftmost character of the substring occurs more than the other.

For example, if $k = 3$, 000101 is a good string, because for all substrings of length 3 (000, 001, 010, and 101) the first character of the substring occurs more than the other character. On the other hand, 1011 is not good, because the property is false for 011.

Given a pattern of length $n$ consisting of characters 0, 1 and ?, find the number of ways to replace question marks with 0 or 1, such that the resulting binary string is good. Since the answer may be large, find it modulo $998\,244\,353$.

考虑一个长度为 $n$ 的二进制字符串和一个奇数 $k$。若对每个长度为 $k$ 的子串，该子串最左侧的字符在子串中出现次数严格多于另一字符，则称该二进制字符串为“好”的。

例如，当 $k = 3$ 时，字符串 000101 是“好”的，因为所有长度为 3 的子串（即 000、001、010 和 101）均满足：子串最左侧的字符在该子串中出现次数严格多于另一字符。而字符串 1011 不是“好”的，因为子串 011 不满足该性质。

给定一个长度为 $n$ 的模式串，其字符由 0、1 和 ? 组成。求将所有 ? 替换为 0 或 1 的方案数，使得所得二进制字符串是“好”的。由于答案可能很大，请对 $998\,244\,353$ 取模。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($3 \le k \le n \le 10^5$, $k$ is odd). The second line contains $n$ characters 0, 1 or ? — the pattern.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^3$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$3 \le k \le n \le 10^5$，且 $k$ 为奇数）。第二行包含 $n$ 个字符，每个字符为 0、1 或 ? —— 表示该模式。

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

For each test case, print the number of ways to replace ? with 0 or 1 such that the resulting string is good, modulo $998\,244\,353$.

对于每个测试用例，输出将 ? 替换为 0 或 1 使得所得字符串为“好”字符串的方案数，对 $998\,244\,353$ 取模。

In the first example, three valid ways to make the pattern good are 00000, 00001, and 00101. In the second example, the only invalid way (out of 16 total ways) is 1001001.

在第一个例子中，使该模式变为“好”的三种有效方式为：00000、00001 和 00101。在第二个例子中，所有 16 种可能方式中唯一无效的方式是 1001001。