H - Prefix Suffix Free
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 100 points
Problem Statement
You are given a string S consisting of lowercase English letters. Count the number of strings T that satisfies all of the following conditions:
- T is a string of the same length as S, consisting of lowercase English letters.
- For all K ( 1 \leq K \leq |S| ), the string formed by the first K letters of S does not coincide with the string formed by the last K letters of T.
Since the answer can be very large, find the number modulo 10^9+7.
Constraints
- 1 \leq |S| \leq 10^6
- S consists of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the number of strings that satisfy the condition, modulo 10^9+7.
Sample Input 1
aa
Sample Output 1
650
For example, T= zz
and ab
satisfy the condition, but ba
or aa
does not.
Sample Input 2
abc
Sample Output 2
16873
Sample Input 3
xrxbaxrxikxrxgvcpuwx
Sample Output 3
352084595