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}\)
ababa
18
ababa has a total of 15 substrings
{a,a,a,b,b,ab,ab,ba,ba,aba,aba,bab,baba,abab,ababa}
count of 'a'=\(3!\)
count of 'b'=\(2!\)
count of 'ab'=\(2!\)
count of 'ba'=\(2!\)
count of 'aba'=\(2!\)
count of 'bab'=\(1!\)
count of 'baba'=\(1!\)
count of 'abab'=\(1!\)
count of 'ababa'=\(1!\)
Their sum is =18.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
No editorial available for this problem.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor