CSES - Datatähti Open 2019 - Bit string
• 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

• $1 \le n \le 100$
• $1 \le n \le 5000$
• $1 \le n \le 5 \cdot 10^5$