Równoważność palindromiczna

Limit pamięci: 64 MB

Dwa słowa i o długości równej nazwiemy równoważnymi palindromicznie, jeśli dla każdej pary liczb oraz , takich, że , podsłowo złożone z liter na pozycjach od -tej do -tej włącznie jest palindromem wtedy i tylko wtedy, gdy palindromem jest podsłowo złożone z liter na tych samych pozycjach.

Dla zadanego słowa oblicz ile jest słów równoważnych mu palindromicznie, zawierających jedynie małe litery alfabetu angielskiego, modulo .

Wejście

W pierwszym wierszu standardowego wejścia znajduje się niepuste słowo złożone z małych liter alfabetu angielskiego, o długości nieprzekraczającej .

Wyjście

Na standardowe wyjście należy wypisać liczbę słów równoważnych palindromicznie do słowa podanego w wejściu, modulo .

Przykład

Dla danych wejściowych:

abba

poprawną odpowiedzią jest:

650

Wyjaśnienie do przykładu: Tylko słowa postaci xyyx są równoważne palindromicznie słowu abba, gdzie x i y są różnymi literami. Ponieważ alfabet angielski ma 26 liter, łącznie jest takich słów.

Autor zadania: Jakub Pachocki.