시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB0000.000%

문제

It is known that the binary positional numeral system works as follows: denoting a nonnegative integer $x$ as a string "$x_k \ldots x_2 x_1 x_0$" of zeroes and ones means that $x = x_k \cdot 2^k + \ldots + x_2 \cdot 2^2 + x_1 \cdot 2^1 + x_0 \cdot 2^0$. The leading zeroes are omitted, so $x_k = 1$, except the case when $x = 0$ which is denoted as "$0$".

The negabinary notation works in a similar way: denoting an number $x$ as a string "$x_k \ldots x_2 x_1 x_0$" of zeroes and ones means that $x = x_k \cdot (-2)^k + \ldots + x_2 \cdot (-2)^2 + x_1 \cdot (-2)^1 + x_0 \cdot (-2)^0$. The leading zeroes are also omitted, so $x_k = 1$, except the case when $x = 0$ which is denoted as "$0$". It turns out that this notation has a unique representation for every integer (as opposed to only nonnegative integers).

Negabinary notation of 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 which has at least $k$ consecutive zeroes in its negabinary representation. Of all such numbers, find the one which has the least absolute value. If there are still several answers, pick the one with the shortest negabinary representation.

입력

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

출력

Print one integer: the answer to the problem.

예제 입력 1

2

예제 출력 1

4