Passwords#11041

Passwords

1 second
128 megabytes
Easy

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.

Input

Given a string (1 \le |s| \le 500000), consisting of lowercase Latin letters.

Output

Print one integer - the desired number of partitions.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading