Sinulle annetaan bittijono, jossa on n bittiä. Tehtäväsi on laskea, monessako yhtenäisessä osajonossa on parillinen määrä ykkösbittejä.

Syöte

Syötteen ainoalla rivillä on bittijono, jossa on n bittiä.

Tuloste

Tulosta yksi kokonaisluku: monessako osajonossa on parillinen määrä ykkösbittejä.

Esimerkki

Syöte:

01011

Tuloste:

6

Osatehtävä 1 (21 pistettä)

• 1 \le n \le 100

Osatehtävä 2 (27 pistettä)

• 1 \le n \le 5000

Osatehtävä 3 (52 pistettä)

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