PRJAN15C - String Play

no tags 

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.

Output

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

Constraints

  • Strings consist of lower-case letters only.
  • 1 ≤ L ≤ 10000006

Sample

Input
abc
aab

Output
8
7

Explanation:

For sample #1, 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".


hide comments
qiujun2009: 2023-07-08 11:16:59

<snip>
[Simes]: read the footer, don't post code here.

Last edit: 2023-07-09 19:30:48
akshayvenkat: 2016-07-10 17:56:03

getting same answer for every testcase i tried on toolkit -_- @Shafaet could u check my submission ?

.:frUstrAteD:.: 2015-06-13 01:55:16

AC using scanf printf in 0.01s
no need of fast i/o :)

(Tjandra Satria Gunawan)(曾毅昆): 2015-02-27 00:56:00

warning: N can rach 10 Million! :-O use the superfast I/O like gets or getchar_unlocked.


Added by:Shafaet
Date:2015-01-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Progrkriya Contest January 2015