E. Лево всегда право
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим бинарную строку длины $$$n$$$ и нечётное число $$$k$$$. Будем называть бинарную строку хорошей, если для каждой подстроки длины $$$k$$$ самый левый символ этой подстроки встречается чаще, чем другой символ.

Например, при $$$k = 3$$$ строка 000101 хорошая, потому что для всех подстрок длины 3 (000, 001, 010 и 101) первый символ подстроки встречается чаще другого. С другой стороны, 1011 не является хорошей, так как свойство нарушается для 011.

Дан шаблон длины $$$n$$$, состоящий из символов 0, 1 и ?. Найдите количество способов заменить вопросительные знаки символами 0 или 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 или ? — шаблон.

Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$10^5$$$.

Выходные данные

Для каждого набора данных выведите количество способов заменить символы ? на 0 или 1 так, чтобы получившаяся строка была хорошей, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
3
5 3
0??0?
7 7
1??1??1
9 5
?????????
Выходные данные
3
15
46
Примечание

В первом примере три подходящих способа сделать шаблон хорошим: 00000, 00001 и 00101. Во втором примере единственный неподходящий вариант (из 16 возможных) — 1001001.