Задача(оллимпиада)

Рассмотрим строку s, состоящую из строчных букв латинского алфавита. Примером такой строки является, например, строка «abba».
Подстрокой строки s называется строка, составленная из одного или нескольких подряд идущих символов строки s. Обозначим как W(s) множество, состоящее из всех возможных подстрок строки s. При этом каждая подстрока входит в это множество не более одного раза, даже если она встречается в строке s несколько раз.
Например, W(«abba») = {«a», «b», «ab», «ba», «bb», «abb», «bba», «abba»}.
Подпоследовательностью строки s называется строка, которую можно получить из s удалением произвольного числа символов. Обозначим как Y(s) множество, состоящее из всех возможных подпоследовательностей строки s. Аналогично W(s), каждая подпоследовательность строки s включается в Y(s) ровно один раз, даже если она может быть получена несколькими способами удаления символов из строки s. Поскольку любая подстрока строки s является также ее подпоследовательностью, то множество Y(s) включает в себя W(s), но может содержать также и другие строки.
Например, Y(«abba») = W(«abba») ∪ {«aa», «aba»}. Знак ∪ обозначает объединение множеств.
Будем называть строку s странной, если для нее W(s) = Y(s). Так, строка «abba» не является странной, а, например, строка «abb» является, так как для нее W(«abb») = Y(«abb») = {«a», «b», «ab», «bb», «abb»}.
Будем называть странностью строки число ее различных странных подстрок. При вычислении странности подстрока считается один раз, даже если она встречается в строке s в качестве подстроки несколько раз. Так, для строки «abba» ее странность равна 7, любая ее подстрока, кроме всей строки, является странной.
Требуется написать программу, которая по заданной строке s определяет ее странность.
Формат входного файла
Входной файл содержит строку s, состоящую из строчных букв латинского алфавита. Строка имеет длину от 1 до 200 000.
Формат выходного файла
Выходной файл должен содержать одно целое число: странность заданной во входном файле строки.
Пример входных и выходных файлов
strange.in strange.out
abba 7


Описание подзадач и системы оценивания
В этой задаче четыре подзадачи. Баллы за каждую подзадачу начисляются только в случае, если все тесты для данной подзадачи успешно пройдены.
Подзадача 1 (29 баллов)
Строка s состоит только из букв «a» и «b». Длина строки s не превышает 50.
Подзадача 2 (12 баллов)
Длина строки s не превышает 50.
Подзадача 3 (25 баллов)
Длина строки s не превышает 1000.
Подзадача 4 (34 балла)
Длина строки s не превышает 200 000.

0