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

**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$