건덕이의 하노이 탑

아래는 건덕이의 하노이 탑에 대한 설명이다. 일반적인 하노이 탑과 규칙이 다름에 유의하여라.

• 장대 3개가 있고 첫 번째 장대에 지름이 서로 다른 $N$개의 원판이 쌓여있다. 원판의 지름이 클 수록 아래에 쌓여있다.
• 한 장대에 있는 원판 한 개를 빼서 다른 장대로 옮길 수 있다. 원판을 다른 장대에 옮길 때, 원판이 없는 장대나 지름이 더 큰 원판 위로만 옮길 수 있다.

건덕이는 장대에 원판이 1개만 있다면 해당 원판을 뺄 수 있다. 건덕이는 중간에 있는 물체도 잘 빼기 때문에, 원판이 2개 이상인 경우 빼려는 원판이 맨 밑만 아니라면 뺄 수 있다.

건덕이가 모든 원판을 세 번째 장대로 옮기기 위해 필요한 원판 이동 횟수의 최솟값을 구해보자.

처음에 첫 번째 장대에 쌓여있는 원판의 개수 $N$이 주어진다. $(1 \le N \le 10^5)$

건덕이가 모든 원판을 세 번째 장대로 옮기기 위해 필요한 원판 이동 횟수의 최솟값을 출력한다.

정답이 $32\textrm{bit}$ 정수 범위를 초과할 수 있음에 유의하세요. C/C++에서는 int 대신 long long을, Java에서는 long 자료형을 사용하는 것을 권장합니다. Python은 기본적으로 큰 수를 지원하므로 정수 자료형을 고려할 필요가 없습니다.