F. Запутанные строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод
вывод
стандартный вывод
Квантовое запутывание происходит, когда две частицы связываются определенным образом независимо от того, насколько далеко они находятся друг от друга в пространстве.

Дана строка $$$s$$$. Две непустые подстроки $$$(a, b)$$$ называются запутанными, если существует (возможно, пустая) связующая строка $$$c$$$ такая, что:

  • Каждое вхождение $$$a$$$ в $$$s$$$ непосредственно следует за вхождением $$$cb$$$;
  • Каждое вхождение $$$b$$$ в $$$s$$$ непосредственно предшествует вхождению $$$ac$$$.

Иными словами, $$$a$$$ и $$$b$$$ встречаются в $$$s$$$ только как подстроки $$$acb$$$. Вычислите общее количество запутанных пар подстрок строки $$$s$$$.

Строка $$$a$$$ является подстрокой $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.

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

Первая и единственная строка содержит строку $$$s$$$ из строчных букв английского алфавита ($$$1 \leq |s| \leq 10^5$$$) — строку, для которой вам нужно посчитать пары запутанных подстрок.

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

Выведите одно целое число, количество запутанных пар подстрок строки $$$s$$$.

Примеры
Входные данные
abba
Выходные данные
1
Входные данные
abacaba
Выходные данные
0
Входные данные
abcabcabcabc
Выходные данные
5
Входные данные
adamant
Выходные данные
82
Примечание

В первом примере единственная запутанная пара — (ab,ba). Для этой пары соответствующая связующая строка $$$c$$$ пуста, так как они встречаются только как подстроки всей строки abba, которая не имеет никаких символов между ab и ba.

Во втором примере запутанных пар нет.

В третьем примере запутанные пары: (a,b), (b,c), (a,c), (a,bc) и (ab,c). Для большинства пар соответствующая связующая строка $$$c$$$ пуста, за исключением пары (a,c), для которой связующая строка $$$c$$$ равна b, так как a и c встречаются только как подстроки строки abc.