In the event of technical difficulties with Szkopuł, please contact us via email at email@example.com.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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 .
The first line of the input contains a non-empty word consisting of lowercase letters of the English alphabet, of length not exceeding .
Your program should output a single integer - the number of words palindromically equivalent to the one given in the input, modulo .
For the input data:
the correct result is:
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.