1607번 - 원숭이 타워

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그는 자신이 원래 살던 곳으로 돌아가고 싶었지만 너무 멀어서 갈 수 없었다. 그래서 그는 자신이 살던 곳의 전통방식으로 지어진 탑을 간절히 생각하며 슬픔을 달래기로 했다. 그 탑의 이름은 원숭이 타워!!

원숭이 타워는 원숭이들이 만든 것이라고는 하지만 원숭이들의 창의력이 부족하여 실제로는 하노이지방의 하노이타워를 응용하여 만든 탑이다. 이제 그 탑을 살펴보자.

위의 그림에 잘 나타나있다. 원숭이 타워가 하노이타워와 다른 점은 기둥을 네 개를 쓴다는 점이다. 이 탑의 목적은 하노이타워와 마찬가지로 디스크들을 1번 기둥에서 4번 기둥으로 모두 옮기는 것이다. 물론, 하노이타워의 규칙을 똑같이 적용해서 옮겨야 한다.

하노이타워의 규칙을 모르는 자들을 위해 하노이타워의 규칙을 설명하겠다.

1. 작은 디스크는 항상 큰 디스크의 위에 놓여야 한다.
2. 한 번에 딱 하나의 디스크를 다른 기둥으로 옮길 수 있다.

이제 원숭이는 머릿속으로 원숭이 타워를 생각하려 하는데 두뇌가 딸려서 잘 계산이 되지 않아 여러분에게 도움을 요청하였다. 처음에 1번기둥에 N개의 크기가 서로 다른 디스크가 쌓여있을 때, N개의 디스크를 모두 4번기둥으로 옮기는 최소회수를 구하는 프로그램을 작성하시오.

첫째 줄에 디스크의 개수 N이 주어진다. N은 1,000,000 이하의 자연수이다.

첫째 줄에 N개의 디스크를 옮기는데 드는 최소회수를 9901로 나눈 나머지를 출력한다.

이 문제는 Frame-Stewart conjecture를 이용해서 풀어야 한다.