루루는 오늘 학교에서 특정한 주제를 바탕으로 리듬이나 선율, 화성 등에 변형을 주어 만든 곡을 의미하는 변주곡에 대해 배웠다.

변주곡에 흥미가 생긴 루루는 자신이 다룰 수 있는 유일한 악기인 피아노 음계를 활용하여 자신만의 변주곡을 만들어보기로 결심했다.

작곡 경험이 부족한 루루는 완벽한 변주곡을 만들 자신이 없었기 때문에, 자신만의 변주곡 작곡 알고리즘을 고안하여 변주곡을 완성했다. 루루가 고안한 알고리즘은 다음과 같다.

< 루루의 변주곡 작곡 알고리즘 >

(1) 길이가 1 이상인 기본 멜로디를 만든다.

(2) 기본 멜로디에서 1개의 꾸밈음을 추가한 변주 멜로디를 원하는 만큼 만든다. 꾸밈음을 추가하는 위치나 사용하는 음계는 자유롭게 정한다.

(3) 만든 변주 멜로디들을 기본 멜로디 뒤에 붙여 변주곡을 완성한다.

열심히 변주곡을 완성한 루루는 문득 기본 멜로디를 따로 적어두지 않았다는 사실을 깨달았다.

기본 멜로디를 찾고 싶던 루루는 어쩔 수 없이 변주곡에서 기본 멜로디가 될 수 있는 모든 멜로디를 하나씩 들어서 확인해보기로 결심했다.

루루가 확인해야 하는 멜로디가 몇 개인지 출력하는 프로그램을 작성하시오.

루루가 작곡한 변주곡이 주어진다. ( 3 <= 변주곡의 길이 <= 100,000 )

루루가 확인해야 하는 멜로디의 개수를 출력한다.