Positive Substring Sum Counting

You are given a string s consisting only of Arabic digits (0-9). A substring sum is defined as the sum of all digits in a contiguous substring of s. Your task is to count how many substrings have a positive substring sum.

Note: A substring consisting entirely of the digit '0' has a sum equal to 0 and should not be counted.

Example: For s = "105", there are 6 substrings in total. Only the substring "0" has a sum of 0, while the sums of all the other substrings are positive. So the answer is 5.

You must design an algorithm that works within 1 second even for large inputs. Good luck!

inputFormat

Input consists of a single line containing a non-empty string s comprised only of digits (0-9).

outputFormat

Output a single integer, which is the number of substrings whose digit sum is positive.

Hint: The total number of substrings in a string of length n is \(\frac{n(n+1)}{2}\). To obtain the desired count, subtract from this number the total number of substrings that consist entirely of zeros. If a block of consecutive zeros has a length of m, then it contributes \(\frac{m(m+1)}{2}\) zero-sum substrings.

sample

105

5