E. Ура, бинарная строка!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Моуф устал от тематических задач, поэтому он решил не использовать никаких тем для этой задачи.

Вам дана бинарная$$$^{\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$$$ и количество раз, которое операция должна быть выполнена, соответственно.

Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длиной $$$n$$$, состоящую только из символов $$$\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{red}{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}$$$