Remote Training on Programming

Рассмотрим строку 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.

Формат выходного файла

Выходной файл должен содержать одно целое число: странность заданной во входном файле строки.

Пример входных и выходных файлов

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

Описание подзадач и системы оценивания

В этой задаче четыре подзадачи. Баллы за каждую подзадачу начисляются только в случае, если все тесты для данной подзадачи успешно пройдены.

Подзадача 1 (29 баллов)

Строка s состоит только из букв «a» и «b». Длина строки s не превышает 50.

Подзадача 2 (12 баллов)

Длина строки s не превышает 50.

Подзадача 3 (25 баллов)

Длина строки s не превышает 1000.

Подзадача 4 (34 балла)

Длина строки s не превышает 200 000.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.