Паролі

Ральф планує зареєструватися на трьох різних сайтах, і для кожного з них він хоче використовувати унікальний пароль. У нього є улюблений рядок s, який він вирішив розділити на три частини: a, b і c. Використовуючи операцію + для об'єднання рядків, ми маємо s = a + b + c. Ральф планує використовувати наступні комбінації як паролі: a + b, b + c і a + c.

Ваше завдання — допомогти Ральфу визначити кількість різних способів розділити рядок s на частини a, b і c так, щоб усі три паролі були різними. Два способи вважаються різними, якщо хоча б один з рядків a, b або c відрізняється.

Вхідні дані

Вам надано рядок s (1 ≤ |s| ≤ 500000), що складається з малих латинських літер.

Вихідні дані

Виведіть одне ціле число — кількість можливих розбиттів.

Приклади