피사의 탑

여러분은 아마 하노이 탑에 얽힌 전설을 들어본 적이 있을 것이다. 전설에 따르면 어느 먼 수도원에는 청동 원판이 있고 그 위에 세 개의 다이아몬드 막대가 세워져 있다. 아주 먼 옛날, 시간이 시작될 무렵 이 수도원의 수도승들이 신들에게 죄를 지었다. 분노한 신들은 막대 하나에 $n$개의 원판을 놓았는데, 모든 원판은 반지름이 달랐고 반지름이 큰 것부터 차례로 쌓여 있었다. 가장 큰 원판이 맨 아래에 있고 그 위에 더 작은 원판이, ..., 가장 작은 원판이 맨 위에 있었다. 수도승들은 원판을 막대 사이로 옮겨야 하는데, 매번 원판을 빈 막대 위에 놓거나 더 큰 원판 위에 놓아야 한다. 신들이 원판을 쌓아 둔 막대에서 다른 막대로 $n$개의 원판을 모두 옮기는 순간, 탑과 함께 신전이 먼지로 변하고 천둥 소리와 함께 세상이 멸망한다.

그런데 최근 페차는 이 전설의 새로운 판본을 읽었다. 이 전설에 따르면 피사의 탑에도 비슷한 퍼즐이 있는데, 두 번째 막대가 기울어져 있다. 두 번째 막대에서는 맨 위에 놓인 여러 원판을 한꺼번에 들어내어 순서를 바꾸지 않고 다른 막대로 함께 옮길 수 있다. 이때 원판 묶음 역시 빈 막대 위에 놓거나, 옮기는 묶음의 맨 아래 원판보다 큰 원판 위에 놓을 수 있다.

전설에 따르면 모든 원판을 첫 번째 막대에서 세 번째 막대로 옮기면 피사의 탑이 더 이상 기울지 않고 똑바로 서게 된다.

페차는 피사 퍼즐에서 모든 원판을 첫 번째 막대에서 세 번째 막대로 옮기는 데 필요한 최소 동작 수가 궁금해졌다. 이 값을 구해 주자.

입력 파일에는 자연수 $n$ 하나가 주어진다 ($1 \le n \le 40$). $n$은 원판의 개수이다.

모든 원판을 세 번째 막대로 옮기는 데 필요한 최소 이동 횟수를 출력한다.

예시에서는 다음과 같이 움직일 수 있다. 작은 원판을 첫 번째 막대에서 세 번째 막대로 옮기고, 그다음 중간 원판을 첫 번째 막대에서 두 번째 막대로 옮기고, 그다음 작은 원판을 세 번째 막대에서 두 번째 막대로 옮기고(중간 원판 위에), 그다음 큰 원판을 첫 번째 막대에서 세 번째 막대로 옮기고, 마지막으로 두 번째 막대에 있는 원판 두 개를 세 번째 막대로 옮긴다. 모두 다섯 번의 동작이 필요하다.