Miguelam patīk palindromi (kuram gan nepatīk, amiright?). Kas var būt labāks par palindromiem? Apakšpalindromi! Palīdzi Miguelam atrast, cik dotajā simbolu virknē ir apakšpalindromi.

Palindroms ir tāda simbolu virkne, kuru var vienādi lasīt no abām pusēm, piemēram, vārds ala ir palindroms, bet vārds sula nav palindroms.

Apakšpalindroms ir apakšvirkne no kādas simbolu virknes, kura atbilst iepriekšējiem nosacījumiem, piemēram, vārdā motocikls apakšvirkne oto ir apakšpalindroms.

Pirmajā rindā dots simbolu virknes garums - N (1 ≤ N ≤ 1 000 000).

Nākamajā rindā seko N latīņu alfabēta mazie burti.

Jāizvada viens skaitlis - kopējais apakšpalindromu skaits.

Autors: Kaspars Kļaviņš.

Apakšpalindromiem nav jābūt unikāliem.

Dotajā piemērā apakšpalindromi ir a, a, b, aba.

• 30% no testa gadījumiem 1 ≤ N ≤ 100.
• 30% no testa gadījumiem 100 < N ≤ 1000.
• 40% bez papildus ierobežojumiem.