G. Считать всегда весело: финал
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
zabutom, Dubmood - Track Tracking
⠀

Вам даны три целых положительных числа $$$x$$$, $$$y$$$ и $$$k$$$.

Вам также дана бинарная строка$$$^{\text{∗}}$$$ $$$a$$$ ($$$|a| = x + y$$$).

Посчитайте количество бинарных строк $$$b$$$, по модулю $$$998\,244\,353$$$, таких что:

  • в $$$b$$$ ровно $$$x$$$ символов $$$\mathtt{0}$$$.
  • в $$$b$$$ ровно $$$y$$$ символов $$$\mathtt{1}$$$.
  • существует целое число $$$i$$$ ($$$1 \leq i \leq x + y - 1$$$) такое, что $$$\min \left( f(b_1 b_2 \ldots b_i), f(b_{i+1} b_{i+2} \ldots b_{x+y})\right) \geq k$$$, где $$$f(s)$$$ обозначает длину самой длинной неубывающей подпоследовательности$$$^{\text{†}}$$$ в $$$s$$$.
  • $$$b$$$ лексикографически больше$$$^{\text{‡}}$$$ чем $$$a$$$.

$$$^{\text{∗}}$$$Бинарная строка — это строка, состоящая только из символов $$$\mathtt{0}$$$ и $$$\mathtt{1}$$$.

$$$^{\text{†}}$$$Последовательность $$$a$$$ является подпоследовательностью последовательности $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ путём удаления нескольких (возможно, нуля или всех) элементов. Например, подпоследовательностями $$$\mathtt{1011101}$$$ являются $$$\mathtt{0}$$$, $$$\mathtt{1}$$$, $$$\mathtt{11111}$$$, $$$\mathtt{0111}$$$, но не $$$\mathtt{000}$$$ и не $$$\mathtt{11100}$$$.

$$$^{\text{‡}}$$$Строка $$$p$$$ лексикографически больше другой строки $$$q$$$, если и только если выполняется одно из следующих условий:

  • $$$q$$$ является префиксом $$$p$$$, но $$$p \ne q$$$; или
  • в первой позиции, где $$$p$$$ и $$$q$$$ различаются, строка $$$p$$$ имеет элемент больше, чем соответствующий элемент в $$$q$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$x$$$, $$$y$$$ и $$$k$$$ ($$$1 \le x, y \le 5000$$$, $$$1 \leq k \lt x + y$$$).

Вторая строка каждого набора входных данных содержит бинарную строку $$$a$$$ ($$$|a| = x+y$$$), состоящую из символов $$$\mathtt{0}$$$ и $$$\mathtt{1}$$$.

Гарантируется, что сумма $$$x$$$ и сумма $$$y$$$ по всем наборам входных данных не превосходят $$$5000$$$.

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

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

Пример
Входные данные
6
1 1 1
00
2 2 2
1110
2 2 1
0101
1 6 3
0000000
4 6 4
0010110010
10 6 7
0010110000101100
Выходные данные
2
0
4
7
106
203
Примечание

Для первого набора входных данных существует две допустимые строки: $$$\mathtt{01}$$$ и $$$\mathtt{10}$$$.

Для третьего набора входных данных существует четыре допустимые строки: $$$\mathtt{0110}$$$, $$$\mathtt{1001}$$$, $$$\mathtt{1010}$$$ и $$$\mathtt{1100}$$$.