32437번 - Fractions are better when continued 다국어

문제

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.

제한

힌트