The Tower of Pisa

Many of you are probably familiar with the legend of the Tower of Hanoi. The legend says that in a distant monastery there is a bronze disk on which three diamond rods are fixed. Long ago, at the very beginning of time, the monks of this monastery offended the gods. The angry gods placed $n$ disks on one of the rods, all disks had different radii and were arranged in decreasing order of radius: the largest disk lay at the bottom, a smaller disk on top of it, ..., and the smallest disk was on top. The monks must move disks between the rods, and each time they must place a disk either on an empty rod or on top of a larger disk. As soon as all $n$ disks are moved from the rod on which the gods stacked them to another rod, the tower along with the temple will turn to dust and the world will perish amid thunderclaps.

However, recently Petya read a new version of the legend. According to this legend, the Tower of Pisa has a similar puzzle, but its second rod is tilted. From the second rod, several disks lying on top can be removed at once and moved together, without changing their order, to another rod. The group of disks can likewise be moved either to an empty rod or onto a disk that is larger than the bottom disk of the group being moved.

According to the legend, when all disks are moved from the first rod to the third, the Tower of Pisa will stop leaning and will stand straight.

Petya wondered what the minimum number of moves is to transfer all disks from the first rod of the Pisa puzzle to the third. Help him find this out.

The input file contains a single positive integer $n$ ($1 \le n \le 40$), the number of disks.

Print a single number: the minimum number of moves required for all disks to end up on the third rod.

In the example, one can act as follows: move the small disk from the first rod to the third, then the middle disk from the first rod to the second, then the small disk from the third to the second (on top of the middle one), then the large disk from the first rod to the third, and finally, as the last move, the pair of disks from the second rod to the third. Five moves are needed in total.