Processing math: 100%
Balance substring - MarisaOJ: Marisa Online Judge

Balance substring

Time limit: 1000 ms
Memory limit: 256 MB

You are given a binary string S. Count the number of non-empty substrings where the number of 0 is equal to the number of 1.

A substring is a consecutive sequence of characters within a string. For example, given the string marisa, ris is a substring, but rsa is not.

Input

  • The first line contains string S.

Output

  • Print 1 integers, the number of sastified substrings.

Constraints

  • 1≤|S|≤105.

Example

Input:

10010

Output:

4