Пароли
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ральф хочет зарегистрироваться на трех сайтах. Для каждого сайта Ральф хочет выбрать свой пароль, причем все три пароля должны быть различны. У Ральфа есть любимая строка $$$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$$$).

Выходные данные

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

Примеры

Входные данные
aabc
Выходные данные
2
Входные данные
ababcb
Выходные данные
9