원숭이 타워

원숭이 타워는 하노이 탑과 같은 규칙을 따르지만, 기둥이 4개인 탑이다.

처음에는 크기가 모두 다른 디스크 N개가 1번 기둥에 쌓여 있다. 목표는 모든 디스크를 4번 기둥으로 옮기는 것이다.

디스크를 옮길 때는 다음 규칙을 지켜야 한다.

1. 큰 디스크를 작은 디스크 위에 올릴 수 없다.
2. 한 번에는 디스크 하나만 다른 기둥으로 옮길 수 있다.

처음 상태에서 N개의 디스크를 모두 4번 기둥으로 옮기는 데 필요한 최소 이동 횟수를 구하시오.

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

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

이 문제는 네 기둥 하노이 탑의 최적 이동 횟수에 대한 Frame-Stewart 추측을 이용해 풀 수 있다.