Task
Time limit:
2000 ms,
Memory limit:
256 Mb
Программисту Васе не повезло - вместо отпуска его послали в командировку на научную конференцию. "Надо повышать уровень знаний", - сказал начальник, "Важная конференция по криптографии, проводится во Франции - а там шифровали еще во времена Ришелье и взламывали чужие шифры еще во времена Виета."
Вася быстро выяснил, что все луврские картины он уже где-то видел, вид Эйфелевой башни приелся ему еще раньше, чем мышка стерла его с коврика, а такие стеклянные пирамиды у нас делают надо всякими киосками и сомнительными забегаловками. Одним словом, смотреть в Париже оказалось просто не на что, рыбу половить негде, поэтому Васе пришлось посещать доклады на конференции.
Один из докладчиков, в очередной раз пытаясь разгадать шифры Бэкона, выдвинул гипотезу, что ключ к тайнам Бэкона можно подобрать, проанализировав все возможные подстроки произведений Бэкона. "Но их же слишком много!" - вслух удивился Вася. "Нет, не так уж и много!" - закричал докладчик, - "Подсчитайте, и вы сами убедитесь!"
Тем же вечером Вася нашел в интернете полное собрание сочинений Бэкона. Он написал программу, которая переработала тексты в одну длинную строку, выкинув из текстов все пробелы и знаки препинания. И вот теперь Вася весьма озадачен - а как же подсчитать количество различных подстрок этой строки?
Входные данные:
На входе дана непустая строка, полученная Васей. Строка состоит только из строчных латинских символов. Ее длина не превосходит 2,000 символов.
Выходные данные:
Выведите количество различных подстрок этой строки.
Пример ввода:
aaba
Пример вывода:
8
Автор: Никита Мякишев