Вам задана бинарная строка (строка, состоящая из символов 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\).
Некоторые строки, которые вы можете получить в первом примере:
Во втором примере \(k = 0\), поэтому можно выбирать только подстроки, состоящие только из символов 0. Перемешивание таких подстрок не меняет строку, поэтому единственная строка, которую можно получить — 10010.
7 2 1100110
16
5 0 10010
1
8 1 10001000
10
10 8 0010011000
2000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач