Substring of a string is defined as a contiguous sequence of characters. And count of substring is the factorial of number of repetitions of that substring in the set containing all the substrings of a given string. Yash's teacher gives him a string and asks him to find the sum of count of all the unique substrings of a string. Since Yash is a noob, he wants your help to solve the above task.

UPDATE: As the number can be very large print the output modulo 1e9+7.

INPUT

The only line of input contains a string of lowercase English alphabets .

OUTPUT

Print the required answer .

CONSTRAINTS

\(1 \leq length of String \leq 4*10^{5}\)