Задача B. Номер циклической перестановки

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

Рассмотрим все различные строки, которые могут быть получены путем циклического сдвига некоторой заданной строки S. Отсортировав их в лексикографическом порядке, сформируем из них упорядоченную последовательность.

Требуется определить номер строки S в полученной последовательности. При этом полагается, что элементы такой последовательности нумеруются с нуля.

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

В заголовке входного файла "input.txt" содержится единственная строка S, состоящая из цифр и строчных букв латинского алфавита.

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

Выходной файл "output.txt" должен содержать порядковый номер исходной строки.

Ограничения

0 < |S| ≤ 2 ⋅ 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
ashat3451abracadabra1b23
12
2
bananabananabananabanana
3

0.106s 0.019s 15