Limits 1s, 512 MB

Milo has a string S of length L. Tutu picks a random prefix and Mota picks a random suffix of S.

Now, Chotku is given a task of concatenating the two strings that Tutu and Mota have chosen, in respective order. Chotku wonders, how many distinct prefix-suffix concatenation is possible out there of string S.

So you know what to do.. Help Chotku!

Input

Input file contains several lines of text. Each line contains a string, S. End of file marks the end of input.

Constraints:

  • S consists of lower-case letters only
  • 1 ≤ L ≤ 10000006

Output

Output one integer per string, denoting the number of distinct prefix-suffix concatenation of the string.

Sample

InputOutput
abc
aab
8
7

For the first input in the sample, the 3 prefixes are “a”, “ab”, “abc”. The 3 suffixes are “c”, “bc”, “abc”. And, the 8 distinct concatenations are, “ac”, “abc”, “aabc”, “abbc”, “ababc”, “abcc”, “abcbc”, “abcabc”.

Submit

Login to submit.

Statistics

48% Solution Ratio
R1shadEarliest, Aug '15
Kuddus.6068Fastest, 0.0s
himuhasibLightest, 1.0 MB
omar24Shortest, 444B
Toph uses cookies. By continuing you agree to our Cookie Policy.