Contest Duration: - (local time) (300 minutes) Back to Home
H - Prefix Suffix Free /

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