시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB41535333588.158%

문제

Little Charles was one of the best competitive programmers in the world. However, he never really liked programming. Now that he is retired, he can dedicate his studies to what he really loves: continued fractions.

To prepare for the upcoming Imensa Competição de Phrações Contínuas (ICPC), he needs to solve the following problem:

Define $p_0 = 1$ as the level $0$ fraction. Then define: $$p_1 = \frac{1}{1+1}$$ as the level $1$ fraction, $p_1$. And also, $$p_2 = \frac{1}{1 + \frac{1}{1+1}}$$ as the level $2$ fraction, $p_2$, and so on.

Given an integer value $N$, help Charles determine the value of the numerator of the fraction $p_N$.

입력

The first and only line contains an integer $N$ ($1 ≤ N ≤ 40$).

출력

The value $p_N$ can be written as a fraction of the form $\frac{a}{b}$, where $a$ and $b$ are coprime. Print a line containing the value of a.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

10

예제 출력 2

89