시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB777100.000%

문제

Palindrom to słowo, które czytane od przodu i od tyłu jest takie samo (na przykład kajak lub anna). Na potrzeby tego zadania przyjmujemy, że palindrom musi mieć co najmniej 2 znaki. Z kolei antypalindrom to słowo, które nie zawiera jako spójny fragment żadnego palindromu. Na przykład słowa bajtek lub bajtocja są antypalindromami, zaś kajak ani olimpiada nie są.

Bajtynka nie lubi palindromów. Właśnie napisała na kartce słowo, które ma być jej pseudonimem w grze internetowej, ale podejrzewa, że w słowie tym są palindromy – co bardzo zepsułoby jej humor. Bajtynka postanowiła więc odciąć z przodu i z końca słowa pewien (być może pusty) fragment, aby pozostała (koniecznie niepusta) część była antypalindromem. Decyzji tej można dokonać na wiele sposobów. Ile dokładnie?

Napisz program, który wyznaczy liczbę sposobów wycięcia początkowego i końcowego fragmentu słowa aby uzyskać niepusty antypalindrom.

입력

W pierwszym (jedynym) wierszu wejścia znajduje się niepusty ciąg małych liter alfabetu angielskiego – słowo Bajtynki. Długość ciągu nie przekracza 100 000 znaków.

출력

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita – liczba różnych sposobów na jakie można wyciąć antypalindrom ze słowa z wejścia zgodnie z powyższymi warunkami. Dwa sposoby uznajemy za różne, jeśli ucinają różną liczbę znaków z przodu lub różną liczbę znaków z tyłu słowa.

예제 입력 1

ababc

예제 출력 1

10

Wyjaśnienie do przykładu: Antypalindromy jakie można uzyskać to: a (na 2 sposoby), b (na 2 sposoby), c, ab (na 2 sposoby), ba, bc oraz abc.

예제 입력 2

mocowocom

예제 출력 2

21

Wyjaśnienie do przykładu: Antypalindromy jakie można uzyskać to: m (na 2 sposoby), c (na 2 sposoby), o (na 4 sposoby), w, mo, moc, om, com, wo, ow, oc (na 2 sposoby), co (na 2 sposoby), cow, woc.

예제 입력 3

abba

예제 출력 3

6

Wyjaśnienie do przykładu: Antypalindromy jakie można uzyskać to: a (na 2 sposoby), b (na 2 sposoby), ab, ba.