Road Network of a Perfect Binary Tree

Time limit2sMemory limit512 MB

Summary

Find the minimum number of cars whose vertex-disjoint paths cover every vertex of a perfect binary tree of height H exactly once.

Level: Medium4 of 10
Topics: Tree, Dynamic programming, Greedy
Solved: No attempts yet

Problem

A country is made of cities and roads, and each road connects two cities. The road network of this country has the shape of a perfect binary tree.

Subin knows the height $H$ of the road network tree. Once the height is known, the number of cities and the number of roads follow: a perfect binary tree of height $H$ has $2^{H+1}-1$ cities and $2^{H+1}-2$ roads.

The picture below shows the case $H = 2$ .

Subin sends cars into the road network. Every car has a start city and a destination city, and it drives along roads from the start city to the destination city without visiting the same city twice. The start city and the destination city may be the same, and such a car visits only that one city.

Subin wants every city to be visited by exactly one car. Write a program that finds the smallest number of cars Subin has to send.

Input

The first line contains $H$ . ( $0 \le H \le 60$ )

Output

Print the smallest number of cars needed so that every city is visited by exactly one car.

The answer always fits in a 64 bit integer.

Examples2

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
2
```
Expected output
```
3
```