Passwords
Ralph wants to register on three sites. Ralph wants to choose a different password for each site, and all three passwords must be different. Ralph has a favorite string s. For the convenience of remembering passwords, Ralph decided to break s into three parts: a, b and c. We will denote sequential writing of two strings by the operation +. Then s = a + b + c. Ralph will use a + b, b + c and a + c as passwords.
Help Ralph to count the number of different ways to split the string s into a, b and c so that the resulting passwords are different. Two ways are different if at least one of the strings a, b or c is different in them.
Input
Given a string s (1 ≤ |s| ≤ 500000), consisting of lowercase Latin letters.
Output
Print one integer - the desired number of partitions.