eolymp
bolt
Try our new interface for solving problems
Problems

Wrong monks

Wrong monks

Time limit 1 second
Memory limit 128 MiB
prb6155-02

In one of the Buddhist monasteries, monks have been rearranging discs for a thousand years. They have three pegs with discs of different sizes. Initially a certain number of disks are put on the first peg and ordered by size - from smallest to largest from top to bottom.Monks must move all discs from the first peg to the third one, satisfying the only condition - any disc cannot be placed on a smaller disc. All three pegs can be used for moves. The monks move one disc in one second. Once they finish their work, the world will come to an end.

Well, is it like a monk to bring the end of the world closer? Wrong monks ... :)

Therefore, we will not be interested in the answer to a question somehow related to the apocalypse, but will be interested in the answer to a more familiar question in our everyday life: What is the least number of moves the monks will be able to complete their work, provided that they move the disks in optimal way?

Input data

Number of discs n (0n64) available to monks. By a strange coincidence, the number of disks in this problem does not exceed the number of cells on an ordinary chessboard.

Output data

Print the smallest number of moves for which the monks can complete their work.

Examples

Input example #1
3
Output example #1
7
Input example #2
1
Output example #2
1
Author Anatoliy Prisyazhnuk
Source ACM ICPC 2013-2014 NEERC Azerbaijan 1/4