두 가지 색 하노이 탑

하노이 탑은 원판을 기둥에 끼워 옮기는 전통적인 퍼즐입니다. 지름이 $1, 2, \dots, n$인 원판 $n$개와 $A$, $B$, $C$라고 부르는 기둥 세 개가 있습니다. 각 원판 가운데에는 구멍이 뚫려 있어 기둥에 끼울 수 있습니다. 처음에는 모든 원판이 기둥 $A$에 있으며, 아래에서 위로 가장 큰 것부터 가장 작은 것 순서로 쌓여 있습니다.

원래의 하노이 탑은 다음 규칙을 지키며 모든 원판을 비어 있는 다른 기둥(예를 들어 $B$)으로 옮기는 놀이입니다.

• 한 번의 이동에서는 어떤 기둥의 맨 위 원판 하나를 집어 다른 기둥의 맨 위에 올릴 수 있습니다.
• 각 기둥에서는 항상 아래일수록 큰 원판, 위일수록 작은 원판이 놓이는 순서가 유지되어야 합니다.

한 기둥에 쌓인 원판들을 하나의 탑이라고 부릅니다. 위 규칙을 정리하면 다음과 같습니다.

• 탑 중간에서 원판을 빼내거나 탑 중간에 원판을 끼워 넣을 수 없습니다.
• 한 번에 두 개 이상의 원판을 옮길 수 없습니다.
• 작은 원판 위에 더 큰 원판을 올릴 수 없습니다.

원래 하노이 탑의 목표는 탑 전체를 최소 이동 횟수로 다른 기둥으로 옮기는 것입니다.

이 문제에서 다루는 두 가지 색 하노이 탑은 이를 조금 변형한 것입니다. 앞서와 마찬가지로 기둥 세 개와 지름이 $1, 2, \dots, n$인 원판 $n$개가 있습니다. 다만 이번에는 지름이 홀수($1, 3, 5, \dots$)인 원판은 흰색, 지름이 짝수($2, 4, 6, \dots$)인 원판은 검은색입니다. 목표는 위 규칙을 지키면서 흰색 원판을 모두 기둥 $B$로, 검은색 원판을 모두 기둥 $C$로 옮기는 것입니다.

흰색 원판을 기둥 $B$에, 검은색 원판을 기둥 $C$에 모으는 데 필요한 최소 이동 횟수를 계산하는 프로그램을 작성하세요.

표준 입력의 첫째 줄에 원판의 개수를 나타내는 정수 $n$ ($0 \le n \le 1000$)이 주어집니다.

흰색 원판을 기둥 $B$에, 검은색 원판을 기둥 $C$에 나누어 놓는 데 필요한 최소 이동 횟수를 표준 출력에 한 줄로 출력합니다.