하노이 탑의 목표 층이 입력되고 목적 달성을 위한 원판의 총 이동 수를 출력하는 프로그램을 작성하십시오.

하노이의 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다.

게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

3층의 탑을 쌓는다면 원판은

1: 1 -> 3

2: 1 -> 2

3: 3 -> 2

4: 1 -> 3

5: 2 -> 1

6: 2 -> 3

7: 1 -> 3

위와 같이 7번 이동하므로 출력되어야할 답은 7입니다.

*재귀호출 또는 스택을 이용하여 문제를 해결하시기를 권장합니다.

입력

탑의 높이(level, 최대 15)

출력

원판의 총 이동 횟수