Циклические суффиксы (Easy)
Рассмотрим строку S = s_1s_2s_3...s_{n - 1}s_n над алфавитом Σ. Циклическим расширением порядка m строки S назовем строку s_1s_2s_3...s_{n - 1}s_ns_1s_2... из m символов; это значит, что мы приписываем строку S саму к себе, пока не получим требуемую длину, и берем префикс длины m.
Циклической строкой Š назовем бесконечное циклическое расширение строки S.
Рассмотрим суффиксы циклической строки Š. Очевидно, существует не более |S| различных суффиксов: (n+1)-ый суффикс совпадает с первым, (n+2)-ой совпадает со вторым, и так далее. Более того, различных суффиксов может быть даже меньше. Например, если S = abab, первые четыре суффикса циклической строки Š - это:
Š_1 = ababababab...Š_2 = bababababa...Š_3 = ababababab...Š_4 = bababababa...
Здесь существует всего два различных суффикса, в то время как |S| = 4.
Отсортируем первые |S| суффиксов Š лексикографически. Если два суффикса совпадают, первым поставим суффикс с меньшим индексом. Теперь нас интересует следующий вопрос: на каком месте в этом списке стоит сама строка Š?
Например, рассмотрим строку S = cabcab:
(1) Š_2 = abcabcabca...(2) Š_5 = abcabcabca...(3) Š_3 = bcabcabcab...(4) Š_6 = bcabcabcab...(5) Š_1 = cabcabcabc...(6) Š_4 = cabcabcabc...
Здесь циклическая строка Š = Š_1 находится на пятом месте.
Вам дана строка S. Ваша задача - найти позицию циклической строки Š в описанном порядке.
Входные данные
Единственная строка S (1 ≤ |S| ≤ 30), состоящая из прописных латинских букв.
Выходные данные
Выведите номер строки Š в описанном порядке среди первых |S| суффиксов.