28817번 - Пароли 다국어

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

Помогите Ральфу посчитать количество различных способов разбить строку $s$ на $a$, $b$ и $c$, чтобы получившиеся пароли были различные. Два способа являются разными, если в них отличается хотя бы одна из строк $a$, $b$ или $c$.

В единственной строке дана строка $s$, состоящая из строчных латинских букв ($1 \le |s| \le 500\,000$).

В единственной строке выведите одно целое число --- искомое количество разбиений.