**Time limit:**1.00 s**Memory limit:**512 MB

You are given a bit string that consists of n bits. Your task is to calculate the number of contiguous substrings that have an even number of ones.

# Input

The only input line has a bit string which consists of n bits.

# Output

Print one integer: the number of substring with an even number of ones.

# Example

Input:

01011

Output:

6

# Subtask 1 (21 points)

- 1 \le n \le 100

# Subtask 2 (27 points)

- 1 \le n \le 5000

# Subtask 3 (52 points)

- 1 \le n \le 5 \cdot 10^5