Candy#1671

Candy

1 second

64 megabytes

Medium

Given a set of numbers ${1, 2, 3, 4, 5, \dots, 2^{n}}$ \{1, 2, 3, 4, 5, \ldots, 2^n\}. Alenka removes $2^{n - 1}$ 2^{n-1} numbers from this set. Alex removes $2^{n - 2}$ 2^{n-2} numbers. Then Alenka removes $2^{n - 3}$ 2^{n-3} numbers. This process continues until only two numbers $a$ and $b$ remain. Then, Alex gives Alenka $∣ a - b ∣$ |a-b| candies. If Alex tries to minimize the candies lost, what is the maximum number of candies Alenka can obtain?

Input

The input contains one natural number $n$ ( $n < 1000$ n < 1000).

Output

Your program should output a single number: the maximum number of candies that Alenka can win.

Examples

Example 1

Loading

{1, 2, 3, 4, 5, \dots, 2^{n}}

2^{n - 1}

2^{n - 2}

2^{n - 3}

∣ a - b ∣

n < 1000