![](https://static.dmoj.ca/media/martor/880b30d2-1fb1-4375-ace9-3a3023d77e7a.png)
The Scratch Cat wants to be a cool coder. He searches for some coding desktop backgrounds, which naturally always contain 1
s and 0
s. The Scratch Cat prefers specifically balanced text consisting of 1
s and 0
s. He defines the imbalance function of string as
, where
is the frequency of
1
s, is the frequency of
0
s, and is the length of string
. The function
represents the percentage of
that is extraneous.
The Scratch Cat determines the "coolness" of a background's text by the number of substrings of
that have an imbalance between
and
, inclusive. The Scratch Cat asks you for help because you are the true cool coder.
Constraints
Each character of is either
1
or 0
.
Subtask 1 [10%]
Subtask 2 [40%]
Subtask 3 [50%]
No additional constraints.
Input Specification
The first line will contain two space-separated integers and
, the minimum and maximum imbalance.
The second line will contain the string , the text in a desktop background.
only consists of
1
or 0
.
Output Specification
Output the number of non-empty substrings with an imbalance in the range . Two substrings are distinct if they are from different segments of
, even if the substrings themselves are identical.
Do not round the function .
Sample Input
33 100
1001
Sample Output
7
Explanation
Below are the imbalances for all substrings of 1001
:
:
1
100
:
10
0
:
0
100
:
100
33.33...
:
00
100
:
0
100
:
1001
0
:
001
33.33...
:
01
0
:
1
100
substrings have an imbalance between
and
.
Comments