Problem Description

You are given a string $ S $ consisting of lowercase English letters. Count the number of strings $ T $ that satisfy 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 $.

Input Format

Input is given from Standard Input in the following format:

$ S $

Output Format

Print the number of strings that satisfy the condition, modulo $ 10^9+7 $.

Sample Input and Output

Sample Input #1

aa

Sample Output #1

650

Sample Input #2

abc

Sample Output #2

16873

Sample Input #3

xrxbaxrxikxrxgvcpuwx

Sample Output #3

352084595

Notes/Hints

Constraints

• $1 \leq |S| \leq 10^6$
• $ S $ consists of lowercase English letters.

Sample Explanation 1

For example, $ T = $ zz and ab satisfy the condition, but ba or aa does not.

见题面 Input 部分

见题面 Output 部分