C. Корова и сообщение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Корова Бесси только что перехватила сообщение, которое Фермер Джон отправил Бургер Куин! Бесси уверена, что в нем скрыто секретное сообщение.

Сообщение представляет из себя строку $$$s$$$, состоящую из строчных букв латинского алфавита. Бесси считает, что строка $$$t$$$ скрыта в строке $$$s$$$, если $$$t$$$ является подпоследовательностью $$$s$$$, индексы которой формируют арифметическую прогрессию. Например, строка aab скрыта в строке aaabb, потому что она получена в индексах $$$1$$$, $$$3$$$ и $$$5$$$, которые формируют арифметическую прогрессию с шагом $$$2$$$. Бесси считает, что любая скрытая строка, которая имеет наибольшее количество вхождений и является скрытым сообщением. Два вхождения подпоследовательности $$$S$$$ различны, если различаются их множества индексов. Помогите Бесси узнать количество вхождений скрытого сообщения!

Например, в строке aaabb, a скрыта $$$3$$$ раза, b скрыта $$$2$$$ раза, ab скрыта $$$6$$$ раз, aa скрыта $$$3$$$ раза, bb скрыта $$$1$$$ раз, aab скрыта $$$2$$$ раза, aaa скрыта $$$1$$$ раз, abb скрыта $$$1$$$ раз, aaab скрыта $$$1$$$ раз, aabb скрыта $$$1$$$ раз и aaabb скрыта $$$1$$$ раз. Количество вхождений скрытого сообщения равно $$$6$$$.

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

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

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

Выведите единственное число  — количество вхождений секретного сообщения.

Примеры
Входные данные
aaabb
Выходные данные
6
Входные данные
usaco
Выходные данные
1
Входные данные
lol
Выходные данные
2
Примечание

В первом примере скрыты следующие строки (с соответствующими множествами индексов):

  • a встречается как $$$(1)$$$, $$$(2)$$$, $$$(3)$$$;
  • b встречается как $$$(4)$$$, $$$(5)$$$;
  • ab встречается как $$$(1,4)$$$, $$$(1,5)$$$, $$$(2,4)$$$, $$$(2,5)$$$, $$$(3,4)$$$, $$$(3,5)$$$;
  • aa встречается как $$$(1,2)$$$, $$$(1,3)$$$, $$$(2,3)$$$;
  • bb встречается как $$$(4,5)$$$;
  • aab встречается как $$$(1,3,5)$$$, $$$(2,3,4)$$$;
  • aaa встречается как at $$$(1,2,3)$$$
  • abb встречается как $$$(3,4,5)$$$
  • aaab встречается как $$$(1,2,3,4)$$$;
  • aabb встречается как $$$(2,3,4,5)$$$;
  • aaabb встречается как $$$(1,2,3,4,5)$$$;
Заметим, что все множества индексов являются арифметическими прогрессиями.

Во втором примере, ни одна скрытая строка не встречается более одного раза.

В третьем примере, скрытым сообщением является одна буква l.