[集训队互测 2022day2]Imbalance
题目描述
定义一个 01 串是平衡的当且仅当它的 01 个数相同。
现在给定 和一个长度为 的 01 串 ，求有多少长度为 且以 为前缀的 01 串满足其不存在长度为 的平衡子串，对 取模。
输入格式
一行，两个整数 ， 和 表示串的长度，平衡串的限制和 的长度。
接下来一行一个长度为 的 01 串表示 。
输出格式
一行一个整数，表示答案模 后的结果。
样例一
input
5 4 2
01
output
3
样例二
input
13 6 0
(此处一个空行)
output
996
数据规模与约定
对于 的数据，保证 且 是偶数。
| 子任务编号 | $n\le$ | 特殊性质 | 分值 | 子任务依赖 |
|---|---|---|---|---|
| $1$ | $20$ | $10$ | ||
| $2$ | $114$ | $k\le 20$ | $10$ | $1$ |
| $3$ | $66$ | $30$ | $1$ | |
| $4$ | $114$ | $m=0$ | $20$ | |
| $5$ | $114$ | $30$ | $2,3,4$ |
时间限制：
空间限制：