Хоч трішки поспати

Обмеження: 1 сек., 512 МіБ

Зеник має рядок \(s\) з малих латинських букв. Він вирішив, що для кожного підрядка цього рядка повинен порахувати, скільки разів він присутній в рядку \(s\), і визначити, скільки підрядків присутні максимальну кількість разів. Рядок дуже великий, тому Зеник вже четверту ніч не заплющує своїх очей і вперто рахує кількості входжень підрядків в його рядок.

Марічка дуже переживає, що Зеник зовсім не спить і вирішила написати програму, котра миттєво знайде відповідь на питання, яке так бентежить Зеника. Оскільки ви пишете програми набагато краще за Марічку, дівчина просить допомоги у вас: за заданим рядком, знайдіть скільки його підрядків входять в нього максимальну кількість разів.

Вхідні дані

Один рядок містить рядок \(s\).

Вихідні дані

Одне число — кількість підрядків рядка \(s\), що мають в ньому найбільшу кількість повторів.

Обмеження

\(1 \le |s| \le 10^6\),

\(s\) містить лише малі латинські літери.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
abcd	10

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
abab	3

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
aaabb	1

Примітки

У першому тесті всі підрядки унікальні, тобто присутні по одному разу.

У другому тесті по два повтори мають підрядки a, b та ab.

У третьому тесті найбільше повторів (три) має підрядок a.