Вам задана бинарная строка (строка, состоящая из символов 0 и/или 1) \(s\) длины \(n\). Вы можете выполнить следующую операцию со строкой \(s\) не более одного раза: выбрать подстроку (непрерывную подпоследовательность) строки \(s\), в которой ровно \(k\) символов 1, и перемешать ее (переставить все символы подстроки в любом порядке).
Посчитайте кол-во различных строк, которые могут быть получены из \(s\), если применить эту операцию не более одного раза.
Выходные данные
Выведите одно целое число — количество различных строк, которые могут быть получены из \(s\), если применить описанную в условии операцию не более одного раза. Так как ответ может быть очень большим, выведите его по модулю \(998244353\).
Примечание
Некоторые строки, которые вы можете получить в первом примере:
- чтобы получить 0110110, вы можете выбрать подстроку с \(1\)-го символа по \(4\)-й символ. Эта подстрока — 1100, и ее перемешиванием можно получить 0110;
- чтобы получить 1111000, вы можете выбрать подстроку с \(3\)-го символа по \(7\)-й символ. Эта подстрока — 00110, и ее перемешиванием можно получить 11000;
- чтобы получить 1100101, вы можете выбрать подстроку с \(5\)-го символа по \(7\)-й символ. Эта подстрока —110, и ее перемешиванием можно получить 101.
Во втором примере \(k = 0\), поэтому можно выбирать только подстроки, состоящие только из символов 0. Перемешивание таких подстрок не меняет строку, поэтому единственная строка, которую можно получить — 10010.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 2
1100110
|
16
|
|
2
|
5 0
10010
|
1
|
|
3
|
8 1
10001000
|
10
|
|
4
|
10 8
0010011000
|
1
|