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.