Count Segments with Exactly m Ones

You are given a binary string b of length n and two integers k and m. Your task is to count the number of contiguous segments (substrings) of length k which contain exactly m ones.

More formally, you need to compute the number of indices i (with \(0 \le i \le n-k\)) such that the substring \(b[i:i+k]\) contains exactly m characters '1'.

Here, the constraints in formula are given by: \(0 \le i \le n-k\) and if we let \(f(i)\) be the number of ones in the substring starting at index \(i\), then the condition is \(f(i) = m\).

Try to design an efficient solution that works well even for large inputs.

inputFormat

The input is read from standard input and consists of two lines:

• The first line contains the binary string b (a string consisting of characters '0' and '1').
• The second line contains two space-separated integers: k and m, where k is the length of the segments and m is the required number of ones in each segment.

outputFormat

Output a single integer (to standard output) which is the number of segments of length k that contain exactly m ones.

1101001
3 2

2