Adrian
시간 제한1초메모리 제한1024 MB
길이가 최대 100만인 소문자 문자열에서 글자를 재배열해 회문을 만들 수 있는 부분 문자열의 개수를 센다.
문제
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).