바샤와 순환 시프트

바샤는 배가 고파서 간식을 찾으러 부엌에 갔다. 냉장고를 열었더니 음식 대신 문자열이 들어 있었다. 그냥 문자열이 아니라 도넛처럼 고리 모양으로 이어진 문자열이었다. 배가 고플 때면 바샤의 머릿속에는 음식 생각이 자주 떠오른다. 호기심이 생긴 바샤는 배고픈 채로 문자열을 손에 들고 돌리기 시작했다. 예를 들어 abacaba를 돌리면 다음 문자열들을 얻을 수 있다:

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

바샤는 문자열을 돌리는 동안 사전순으로 가장 작은 순환 시프트가 몇 번 나오는지 셀 수 있다면 냉장고에 음식이 나타날 것이라고 생각했다. 배고플 때는 엉뚱한 생각도 떠오른다. 바샤를 도와주자. 그렇지 않으면 바샤는 계속 굶게 된다.

길이가 $n$인 문자열 $s$의 순환 시프트는 원래 문자열의 처음 $k$개 문자($0 \leq k < n$)를 떼어 뒤에 붙여 만든 문자열이다. 주어진 문자열의 모든 순환 시프트 중에서 사전순으로 가장 작은 순환 시프트가 몇 번 나오는지 구하라.

입력 파일의 첫 줄에는 바샤가 발견한 문자열 $S$가 주어진다. 문자열은 비어 있지 않으며 소문자 라틴 문자로만 이루어져 있고, 길이는 10,000,000을 넘지 않는다.

구하는 순환 시프트의 개수를 하나의 수로 출력한다.