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