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

3

7

1

1