CF1622D.Shuffle

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.

给你一个长度为 $n$ 的二进制字符串（即仅由字符 0 和/或 1 组成的字符串）$s$。你最多可以对字符串 $s$ 执行以下操作一次：选择 $s$ 的一个子串（即一段连续的子序列），该子串中恰好包含 $k$ 个字符 1，然后对该子串进行洗牌（即任意重排该子串中的字符）。

请计算：通过对 $s$ 最多执行一次上述操作，所能得到的不同字符串的总数。

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.

第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 5000$；$0 \le k \le n$）。

第二行包含一个长度为 $n$ 的字符串 $s$，由字符 0 和/或 1 组成。

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$.

输出一个整数——即通过对字符串 $s$ 至多执行一次所述操作所能得到的不同字符串的个数。由于答案可能很大，请对 $998244353$ 取模后输出。

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.

第一个样例中可以得到的一些字符串：

• 要得到 0110110，可取第 $1$ 个字符到第 $4$ 个字符的子串，即 1100，并重排其字符得到 0110；
• 要得到 1111000，可取第 $3$ 个字符到第 $7$ 个字符的子串，即 00110，并重排其字符得到 11000；
• 要得到 1100101，可取第 $5$ 个字符到第 $7$ 个字符的子串，即 110，并重排其字符得到 101。

在第二个样例中，$k = 0$，因此你只能选择仅由 0 字符组成的子串。重排这些子串不会改变字符串本身，因此唯一能得到的字符串是 10010。