eolymp
bolt
Try our new interface for solving problems
Problems

Passwords

Passwords

Time limit 1 second
Memory limit 128 MiB

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 data

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

Output data

Print one integer - the desired number of partitions.

Examples

Input example #1
aabc
Output example #1
2
Input example #2
ababcb
Output example #2
9
Source 2018 Цикл Интернет-олимпиад для школьников, вторая командная олимпиада сезона, базовая номинация, 10 ноября, Задача H