You are given a binary string s (only the characters 0 and 1). Count the number of contiguous substrings that contain an equal number of 0s and 1s and in which all the 0s and all the 1s are grouped together (that is, the substring looks like 0...01...1 or 1...10...0).
Substrings that occur at different positions are counted separately, even if they look the same.
Input format
A single line: the binary string s (possibly empty).
Output format
A single integer: the number of qualifying substrings.
Constraints
- 0 <= length of
s<= 100000 scontains only the characters0and1.