Adrian

Mladi Adrian se izgubio tumarajući po bespućima Engleske i naletio na čarobnjaka koji mu je dao papir na kojemu je bila zapisana neka riječ. Čarobnjak mu je naredio da prebroji koliko u toj riječi postoji podriječi od kojih se premetanjem slova u njoj može dobiti palindrom. Drugim riječima, zanima ga koliko postoji parova indeksa (i, j) (1 ≤ i ≤ j ≤ duljina riječi), takvih da podriječ koju dobijemo kada iz zadane riječi uzmemo samo slova od i-tog do j-tog uključivo, možemo premetanjem slova pretvoriti u palindrom. Adrian se uplašio i zapitao čarobnjaka: “Palindrom? O čemu govoriš? Što je to?”. Čarobnjak mu je pojasnio da se radi o riječi koja ostane ista kada joj se obrne poredak slova, primjerice riječ topot. Pomozite Adrianu riješiti čarobnjakovu smicalicu.

U prvom i jedinom retku nalazi se riječ od najviše 1 000 000 malih slova engleske abecede.

U jedini redak ispišite traženi broj podriječi iz teksta zadatka.

Opis drugog primjera: Podriječi su: t, p, o, o, t, oo, poo (premetanjem može postati opo), oot (premetanjem može postati oto) i tpoot (premetanjem može postati topot).