Substring
Medium
Execution time limit is 2 seconds
Runtime memory usage limit is 64 megabytes
Given a string s. Count the number of different substrings. Empty substrings should not be counted.
Input
One line s, consisting of lowercase Latin letters. The string length does not exceed 20 000 characters.
Output
Print the number of different substrings of s.
Examples
Input #1
Answer #1
Submissions 928
Acceptance rate 12%