A stack of n graduated disks sits on the first of three spires, largest at the bottom. To relocate the whole stack to another spire you may move one disk at a time onto a spire, and you may never place a larger disk on top of a smaller one. It is a classic fact that relocating the top k disks reduces to relocating the top k-1 disks, moving the largest, then relocating the k-1 disks again.
Print the exact minimum number of single-disk moves required to relocate the entire tower of n disks. The answer can be large, so print the full exact integer (not modulo anything).
Input format
A single line with one integer n, the number of disks.
Output format
A single integer: the minimum number of moves.
Constraints
- 0 <= n <= 100