30845번 - Вася и Циклические Сдвиги 다국어

문제

Однажды Василий проголодался и пошел на кухню подкрепиться. Но каково было его удивление, когда, открыв холодильник, он обнаружил там не привычные продукты, а строку! Причем не просто строку, а зацикленную, прямо как бублик (ассоциации с едой часто приходят Васе в голову, когда он голоден). Загадочная строка заинтересовала любопытного, но все еще голодного Василия, и он начал ее вертеть в руках. Например, если вертеть строку abacaba, то можно получить следующие строки:

• abacaba
• bacabaa
• acabaab
• cabaaba
• abaabac
• baabaca
• aabacab

И тут Василия осенило: если он сможет посчитать, сколько раз в процессе кручения строки получается лексикографически минимальная строка, то еда магическим образом появится в холодильнике (странные идеи часто приходят Васе в голову, когда он голоден). Помогите Васе, иначе он так и будет сидеть голодным.

Более формально, вам дана строка. Циклическим сдвигом строки s длины n называется строка, полученнная из исходной путем отбрасывания первых 0 ⩽ k < n символов и приписывания их в конец. Необходимо посчитать, сколько раз среди всех циклических сдвигов строки встречается лексикографически минимальный циклический сдвиг.

입력

Единственная строка входного файла содержит строку S, найденную Василием. Она непуста, состоит из маленьких латинских букв, и её длина не превосходит 10 000 000.

출력

Выведите единственное число — искомое количество минимальных циклических сдвигов.

제한

힌트