Mr. Chaos is a high school student. Teachers always ask him to write a lot of compositions, but he isn't interested in it at all. Tired of generating meaningless words by himself, he invented a machine to help him.

His teacher has posted the model article -- string , on the blackboard. His machine can generate any lowercase string of length at a time. For a fixed string , the scoring method is simple: for any pair of integers such that the substring is a palindrome, the final score will be added by the number that occurs in . Formally, let's define as the string , a string is palindromic if it remains the same string when reversing, and the occurrence time  of in , , is the number of pairs of such that . Then, the value of , namely , is defined as

For example, given , when the machine generated a string , one of its palindromic substrings will be . is because  occurs in twice. Note that there are two in this case, and they are considered as different substrings and calculated twice.

As Mr. Chao's best friend, you are asked to tell him the sum of value of all the that his machine can generate.

You accept this mission without thinking twice. However, it seems that you are getting into trouble, because the teacher makes revisions on string . Each time the last character will be deleted or a new character will be added to the end. So now you have to answer the question for times.

Formally, let be the set of all strings of length that only contain lowercase English letters. You are going to calculate this formula

at the beginning and after each revision of , that is, in total times. As the answer may be too large, you only need to output its remainder modulo