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

Вам задана бинарная строка (строка, состоящая из символов 0 и/или 1) $$$s$$$ длины $$$n$$$. Вы можете выполнить следующую операцию со строкой $$$s$$$ не более одного раза: выбрать подстроку (непрерывную подпоследовательность) строки $$$s$$$, в которой ровно $$$k$$$ символов 1, и перемешать ее (переставить все символы подстроки в любом порядке).

Посчитайте кол-во различных строк, которые могут быть получены из $$$s$$$, если применить эту операцию не более одного раза.

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

В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 5000$$$; $$$0 \le k \le n$$$).

Во второй строке задана строка $$$s$$$ длины $$$n$$$, состоящая из символов 0 и/или 1.

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

Выведите одно целое число — количество различных строк, которые могут быть получены из $$$s$$$, если применить описанную в условии операцию не более одного раза. Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.

Примеры
Входные данные
7 2
1100110
Выходные данные
16
Входные данные
5 0
10010
Выходные данные
1
Входные данные
8 1
10001000
Выходные данные
10
Входные данные
10 8
0010011000
Выходные данные
1
Примечание

Некоторые строки, которые вы можете получить в первом примере:

  • чтобы получить 0110110, вы можете выбрать подстроку с $$$1$$$-го символа по $$$4$$$-й символ. Эта подстрока — 1100, и ее перемешиванием можно получить 0110;
  • чтобы получить 1111000, вы можете выбрать подстроку с $$$3$$$-го символа по $$$7$$$-й символ. Эта подстрока — 00110, и ее перемешиванием можно получить 11000;
  • чтобы получить 1100101, вы можете выбрать подстроку с $$$5$$$-го символа по $$$7$$$-й символ. Эта подстрока —110, и ее перемешиванием можно получить 101.

Во втором примере $$$k = 0$$$, поэтому можно выбирать только подстроки, состоящие только из символов 0. Перемешивание таких подстрок не меняет строку, поэтому единственная строка, которую можно получить — 10010.