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

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

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