给定一个二进制字符串(即由字符 0 和/或 1 组成的字符串)$$$s$$$,长度为 $$$n$$$。您最多可以对字符串 $$$s$$$ 执行以下操作:选择 $$$s$$$ 中恰好包含 $$$k$$$ 个字符 1 的子字符串(连续子序列),然后将其打乱(根据需要对子字符串中的字符重新排序)。
计算最多执行一次此操作从 $$$s$$$ 中可以获得的不同字符串的数量。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 5000$$$; $$$0 \le k \le n$$$)。
第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,由字符 0 和/或 1 组成。
输出
打印一个整数——最多执行一次所描述的操作从$$$s$$$中获得的不同字符串的数量。由于答案可能很大,因此输出它对 $$$998244353$$$ 取模。
示例
输入 #1
7 2 1100110
输出 #1
16
输入 #2
5 0 10010
输出 #2
1
输入 #3
8 1 10001000
输出 #3
10
输入#4
10 8 0010011000
输出#4
1
注意
您可以在第一个示例中获取一些字符串:
- 要获得0110110,可以取出从$$$1$$$-第一个字符到第$$$4$$$-个字符的子串,即1100,并将其字符重新排序,得到0110;
- 要获得1111000,可以取出从$$$3$$$第一个字符到第$$$7$$$个字符的子字符串,即00110,并将其字符重新排序,得到11000;
- 要获得 1100101,您可以取出从第 $$$5$$$ 字符到第 $$$7$$$ 字符的子字符串,即 110,并将其字符重新排序以获得 101。
在第二个示例中,$$$k = 0$$$,因此您只能选择仅由 0 个字符组成的子字符串。对它们重新排序根本不会改变字符串,因此您可以获得的唯一字符串是 10010。