Shuffle
Contest: Educational Codeforces Round 120 (Rated for Div. 2)
Difficulty rating: 2000
Tags: combinatorics, math, two pointers

You are given a binary string (i. e. a string consisting of characters 0 and/or 1) $$$s$$$ of length $$$n$$$. You can perform the following operation with the string $$$s$$$ at most once: choose a substring (a contiguous subsequence) of $$$s$$$ having exactly $$$k$$$ characters 1 in it, and shuffle it (reorder the characters in the substring as you wish).

Calculate the number of different strings which can be obtained from $$$s$$$ by performing this operation at most once.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 5000$$$; $$$0 \le k \le n$$$).

The second line contains the string $$$s$$$ of length $$$n$$$, consisting of characters 0 and/or 1.

Output format:
Print one integer — the number of different strings which can be obtained from $$$s$$$ by performing the described operation at most once. Since the answer can be large, output it modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
Some strings you can obtain in the first example:

- to obtain 0110110, you can take the substring from the $$$1$$$-st character to the $$$4$$$-th character, which is 1100, and reorder its characters to get 0110;
- to obtain 1111000, you can take the substring from the $$$3$$$-rd character to the $$$7$$$-th character, which is 00110, and reorder its characters to get 11000;
- to obtain 1100101, you can take the substring from the $$$5$$$-th character to the $$$7$$$-th character, which is 110, and reorder its characters to get 101.

In the second example, $$$k = 0$$$ so you can only choose the substrings consisting only of 0 characters. Reordering them doesn't change the string at all, so the only string you can obtain is 10010.

Example input:
7 2
1100110

Example output:
16

Example input:
5 0
10010

Example output:
1

Editorial:
We could iterate on the substrings we want to shuffle and try to count the number of ways to reorder their characters, but, unfortunately, there's no easy way to take care of the fact that shuffling different substrings may yield the same result.
Instead, we will iterate on the first and the last character that are changed. Let these characters be $$$i$$$ and $$$j$$$. First of all, let's check that they can belong to the same substring we can shuffle — it is the case if the string contains at least $$$k$$$ characters 1, and the substring from the $$$i$$$-th character to the $$$j$$$-th character contains at most $$$k$$$ characters 1.
Then, after we've fixed the first and the last characters that are changed, we have to calculate the number of ways to shuffle the characters between them (including them) so that both of these characters are changed. Let's calculate $$$c_0$$$ and $$$c_1$$$ — the number of characters 0 and 1 respectively in the substring. Then, we need to modify these two values: for example, if the $$$i$$$-th character is 0, then since it is the first changed character, it should become 1, so we need to put 1 there and decrease $$$c_1$$$ by one. The same for the $$$j$$$-th character. Let $$$c'_0$$$ and $$$c'_1$$$ be the values of $$$c_0$$$ and $$$c_1$$$ after we take care of the fact that the $$$i$$$-th and the $$$j$$$-th character are fixed. The remaining characters can be in any order, so the number of ways to arrang them is $$${{c'_0 + c'_1}\choose{c'_0}}$$$.
We can add up these values for all pairs ($$$i, j$$$) such that we can shuffle a substring containing these two characters. We won't be counting any string twice because we ensure that $$$i$$$ is the first changed character, and $$$j$$$ is the last changed character. Don't forget to add $$$1$$$ to the answer — the string we didn't count is the original one.
This solution works in $$$O(n^2)$$$, but the problem is solvable in $$$O(n)$$$.