Counting Substrings with More Ones than Zeros

Consider a binary string S composed only of the characters '0' and '1'. We define a substring S[i...j] (1-indexed) as valid if the number of '1's in the substring is strictly greater than the number of '0's. Formally, letting \(\#1(S[i\dots j])\) denote the count of 1's and \(\#0(S[i\dots j])\) denote the count of 0's in the substring, the condition is:

$$\#1(S[i\dots j]) > \#0(S[i\dots j])$$

Your task is to compute the total number of valid substrings for a given binary string S.

inputFormat

The input consists of a single line containing the binary string S.

outputFormat

Output a single integer representing the number of substrings in which the number of '1's is greater than the number of '0's.

sample

101

3