Merkkijonon osajono on yhtenäinen merkkijonosta valittu osa. Esimerkiksi merkkijono ABAC sisältää osajonot A, B, A, C, AB, BA, AC, ABA, BAC ja ABAC.

Sinulle on annettu merkkijono, ja tehtäväsi on laskea, monessako merkkijonon osajonossa ensimmäinen ja viimeinen merkki on sama.

Esimerkiksi merkkijonossa ABAC vastaus on 5, koska osajonoissa A, B, A, C ja ABA ensimmäinen ja viimeinen merkki on sama.

Syöte

Syötteen ainoalla rivillä on merkkijono, jossa on n merkkiä ja jokainen merkki on välillä A–Z.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: haluttujen osajonojen määrä.

Esimerkki 1

Syöte:

ABAC

Tuloste:

5

Esimerkki 2

Syöte:

AABACBABBA

Tuloste:

26

Osatehtävä 1 (12 pistettä)

• 1 \le n \le 100

Osatehtävä 2 (27 pistettä)

• 1 \le n \le 5000

Osatehtävä 3 (61 pistettä)

• 1 \le n \le 10^5