eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Шифр Бекона

Шифр Бекона

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Програмісту Васі не повезло - замість відпустки його відправили у відрядження, на наукову конференцію. Потрібно підвищувати рівень знань, сказав начальник, важлива конференція по криптографії, проводиться у Франції - а там шифрували ще за часів Рішельє та зламували чужі шифри ще у часи Вієта.

Вася швидко вияснив, що усі луврські картини він вже десь бачив, вид ейфелевої вежі приївся йому ще раніше, ніж мишка стерла його з коврику, а такі скляні піраміди у нас роблять над усілякими кіосками та сумнівними забігайлівками. Одним словом, дивитись у Парижі виявилось просто не на що, рибу половити ніде, тому Васі прийшлось відвідувати доповіді на конференції. Один з доповідачів, який у черговий раз намагався розгадати шифри Букона, висунув гіпотезу, що ключ до тайн Бекона можна підібрати, проаналізувавши усі можливі підрядки творів Бекона. "Але ж їх же занадто багато!" - вголос здивувався Вася. "Ні, не так вже й багато!" - закричав доповідач - "підрахуйте і ви самі переконаєтесь!".

Тим же вечором Вася знайшов в Інтернеті повне зібрання творів Бекона. Він написав програму, яка обробляла тексти у один довгий рядок, викинув з текстів усі пропуски та розділові знаки. І ось тепер Вася дуже стурбований - а як же підрахувати кількість різних підрядків цього рядка?

Вхідні дані

На вході задано непорожній рядок, отриманий Васею. Рядок складається лише з рядкових латинських символів. Його довжина не перевищує 2000 символів.

Вихідні дані

Виведіть кількість різних підрядків цього рядка.

Приклад

Вхідні дані #1
aaba
Вихідні дані #1
8