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 . For the convenience of remembering passwords, Ralph decided to break into three parts: , and . 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 into , and so that the resulting passwords are different. Two ways are different if at least one of the strings , or is different in them.
Given a string (1 \le |s| \le 500000), consisting of lowercase Latin letters.
Print one integer - the desired number of partitions.
Example 1
Example 2