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.