Рабочее место участника

Рассмотрим строку `s`, состоящую из строчных букв латинского алфавита. Примером такой строки является, например, строка «abba».

Подстрокой строки s называется строка, составленная из одного или нескольких подряд идущих символов строки `s`. Обозначим как `W(s)` множество, состоящее из всех возможных подстрок строки s. При этом каждая подстрока входит в это множество не более одного раза, даже если она встречается в строке `s` несколько раз.

Например, `W(tt{«"abba"»})\ =\ {tt{«a»},\ tt{«b»},\ tt{«"ab"»},\ tt{«"ba"»},\ tt{«b""b»},\ tt{«"abb"»},\ tt{«"bba"»},\ tt{«"abba"»}\ }`.

Подпоследовательностью строки `s` называется строка, которую можно получить из `s` удалением произвольного числа символов. Обозначим как `Y(s)` множество, состоящее из всех возможных подпоследовательностей строки `s`. Аналогично `W(s)`, каждая подпоследовательность строки `s` включается в `Y(s)` ровно один раз, даже если она может быть получена несколькими способами удаления символов из строки `s`. Поскольку любая подстрока строки `s` является также ее подпоследовательностью, то множество `Y(s)` включает в себя `W(s)`, но может содержать также и другие строки.

Например, `Y(tt{«"abba"»}) = W(tt{«"abba"»}) uu {tt{«"aa"»},\ tt{«"aba"»}\ }`. Знак `uu` обозначает объединение множеств.

Будем называть строку `s` странной, если для нее `W(s)` = `Y(s)`. Так, строка «abba» не является странной, а, например, строка «abb» является, так как для нее `W(tt{«"abb"»})\ =\ Y(tt{«"abb"»})\ =\ {tt{«a»},\ tt{«b»},\ tt{«"ab"»},\ tt{«b""b»},\ tt{«"abb"»}\ }`.

Будем называть странностью строки число ее различных странных подстрок. При вычислении странности подстрока считается один раз, даже если она встречается в строке `s` в качестве подстроки несколько раз. Так, для строки «abba» ее странность равна 7, любая ее подстрока, кроме всей строки, является странной.

Требуется написать программу, которая по заданной строке `s` определяет ее странность.

Входной файл содержит строку `s`, состоящую из строчных букв латинского алфавита. Строка имеет длину от 1 до `200 000`.

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

abba

7

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

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

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

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

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

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