#P18611. Distinct Subsequences

Distinct Subsequences

Distinct Subsequences

给定一个长度为n的二进制字符串s和一个整数k。请计算s中长度恰为k的不同子序列数量,答案对998244353取模。

子序列由按原顺序选取若干字符得到,所选位置不要求连续。“不同”按得到的字符串内容区分;同一个字符串即使能用多种下标选择得到,也只计算一次。

输入格式

第一行两个整数n、k。第二行一个长度为n、只含0和1的字符串s。本题只有一个测试用例。

输出格式

输出一个整数,为长度恰为k的不同子序列数量对998244353取模的结果。

数据范围

1<=k<=n<=200000。

样例输入 1

5 3
00110

样例输出 1

5

样例输入 2

12 8
000111000000

样例输出 2

12

样例输入 3

31 12
1110100111110110101111010100010

样例输出 3

3985