English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Równoważność palindromiczna (pal)
Palindromic Equivalence
Memory limit: 64 MB
We will call two words 
and 
of length 
palindromically equivalent, if
for every pair of numbers 
and 
such that 
, the subword of 
consisting of letters
from positions 
to 
, inclusively, is a palindrome if and only if the subword of 
consisting of letters from the same set of
positions is a palindrome.
For a given word, your task is to compute the number of words over the English alphabet that are palindromically equivalent to it, modulo 
.
Input
The first line of the input contains a non-empty word consisting of lowercase letters of the English alphabet, of length not exceeding 
.
Output
Your program should output a single integer - the number of words palindromically equivalent to the one given in the input, modulo 
.
Example
For the input data:
abba
the correct result is:
650
Explanation of the example: Only words of the form xyyx are palindromically equivalent to
abba, where x and y are distinct letters.
The English alphabet contains 26 letters, consequently there are 
such words in total.
Task author: Jakub Pachocki.