Double Disk Towers of Hanoi

There are three pegs: A, B, and C. Initially, peg A has 2n disks, consisting of n distinct sizes with two identical disks of each size (they are indistinguishable). The disks on each peg are arranged so that they are in non-decreasing order from top to bottom (i.e. a disk can be placed on top of another disk only if its size is not larger than the disk below).

The goal is to move all the disks from peg A to peg C using peg B as an auxiliary storage. Only one disk can be moved at a time, and after each move the disks on every peg must remain in the required order.

Let \( A_n \) be the minimum number of moves required to transfer the 2n disks. It can be shown that the answer is given by the formula:

\( A_n = 4 \cdot 3^{n-1} - 1 \)

For a given input n, output \( A_n \).

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 20), representing the number of distinct disk sizes.

outputFormat

Output the minimum number of moves \(A_n\) required to move the disks from peg A to peg C.

sample

1

3