Negative Base

Time limit2sMemory limit512 MB

Summary

Find the integer of least absolute value whose negabinary (base -2) representation contains at least k consecutive zeroes, breaking ties by shortest representation.

Level: Medium6 of 10
Topics: Math, Bit manipulation, Brute force, Implementation
Solved: No attempts yet

Problem

The binary positional numeral system works as follows. Writing a nonnegative integer $x$ as a string " $x\_k \ldots x\_2 x\_1 x\_0$ " of zeroes and ones means $x = x\_k \cdot 2^k + \ldots + x\_2 \cdot 2^2 + x\_1 \cdot 2^1 + x\_0 \cdot 2^0$ . Leading zeroes are omitted, so $x\_k = 1$ , except when $x = 0$ , which is written as " $0$ ".

The negabinary notation works in a similar way. Writing a number $x$ as a string " $x\_k \ldots x\_2 x\_1 x\_0$ " of zeroes and ones means $x = x\_k \cdot (-2)^k + \ldots + x\_2 \cdot (-2)^2 + x\_1 \cdot (-2)^1 + x\_0 \cdot (-2)^0$ . Leading zeroes are omitted here as well, so $x\_k = 1$ , except when $x = 0$ , which is written as " $0$ ". This notation has a unique representation for every integer, not only for nonnegative integers.

Negabinary notation of the numbers from $-7$ to $8$ :

$-7$	$1001$	$1$	$1$
$-6$	$1110$	$2$	$110$
$-5$	$1111$	$3$	$111$
$-4$	$1100$	$4$	$100$
$-3$	$1101$	$5$	$101$
$-2$	$10$	$6$	$11010$
$-1$	$11$	$7$	$11011$
$0$	$0$	$8$	$11000$

Given an integer $k$ , find a number whose negabinary representation contains at least $k$ consecutive zeroes. Among such numbers, find the one with the least absolute value. If several answers remain, pick the one with the shortest negabinary representation.

Input

The first line of input contains an integer $k$ ( $1 \le k \le 30$ ).

Output

Print one integer: the answer to the problem.

Examples1

Example 1
Input
```
2
```
Expected output
```
4
```