CF1622D Shuffle

给定一个长度为 $n$ 的二进制字符串（即仅包含字符 $0$ 和/或 $1$ 的字符串）$s$。你最多可以对字符串 $s$ 执行一次如下操作：选择一个恰好包含 $k$ 个字符 $1$ 的子串（连续子序列），并对该子串进行任意重排（即可以任意改变该子串内字符的顺序）。 请计算通过最多执行一次上述操作，可以从 $s$ 得到多少个不同的字符串。由于答案可能很大，请输出答案对 $998244353$ 取模后的结果。

第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 5000$，$0 \le k \le n$）。 第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 $0$ 和/或 $1$ 组成。

输出一个整数，表示通过最多执行一次描述中的操作，可以得到多少个不同的字符串。由于答案可能很大，请输出答案对 $998244353$ 取模后的结果。

在第一个样例中，你可以得到的一些字符串如下： - 要得到 0110110，你可以选择第 $1$ 个字符到第 $4$ 个字符组成的子串 1100，并将其重排为 0110； - 要得到 1111000，你可以选择第 $3$ 个字符到第 $7$ 个字符组成的子串 00110，并将其重排为 11000； - 要得到 1100101，你可以选择第 $5$ 个字符到第 $7$ 个字符组成的子串 110，并将其重排为 101。 在第二个样例中，$k=0$，因此你只能选择仅包含 $0$ 的子串。对其重排不会改变字符串，所以你只能得到 10010 这一种字符串。 由 ChatGPT 4.1 翻译