4032. 体育课

【题目描述】

某校上体育课，共有n名学生，男生女生都有，上体育课时需要按既定顺序排成一排，有些同学不爱运动，会在上体育课时逃课，来上课的同学为了给逃课的同学打掩护，会自动左右对齐，弥补逃课同学空下来的位置。上课人数较多时，体育老师不会发现有人逃课，但人数太少时就会被发现，当上课人数小于等于m时，体育老师发现有人逃课会非常生气，体育特别喜欢数学，当他生气时他会把上课的学生看成一个个数字，男同学会看成1，女同学看成0。来上课的一排学生就是一个二进制数，这种情况会有很多种，因为每次上课会有不同的学生组合逃课。体育老师喜欢男生，只有最左面是男生的情况才被考虑。被认为是数学神童的你需要计算所有情况老师眼中的二进数转换成十进制的和，这个数可能很大，只需输出模P(P=998244353)的余数即可。

【输入格式】

第一行两个正整数n,m，中间用空格隔开

第二行一个长度为n的01串，表示所有n名同学，1表示男生，0表示女生

【输出格式】

输出一个正整数，意义如题所示。

【样例输入】

4 2
1001

【样例输出】

9

【提示】

样例解释：

共有A、B、C、D，4位同学，其中A、D是男生，B、C是女生。小于m（m=2)的情况有4种，只有1个人，A,B,C,D对应二进制数为1，0，0，1，和为2。等于m的情况有6种,AB、AC、AD、BC、BD、CD，对应进制数为10、10、11、00、01、01，其中后3种情况不符合最左面是男生的条件，和为2+2+3=7。输出的是两种情况的和，最终结果为2+7=9。

对于20%的数据n<=4;

对于30%的数据n<=10,m<=4

对于100%的数据n<=100000,m<=10

大样例

【来源】

在此键入。