Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 100 points
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.
- 1 \leq |S| \leq 10^6
- S consists of lowercase English letters.
Input is given from Standard Input in the following format:
Print the number of strings that satisfy the condition, modulo 10^9+7.
Sample Input 1
Sample Output 1
For example, T=
ab satisfy the condition, but
aa does not.
Sample Input 2
Sample Output 2
Sample Input 3
Sample Output 3