Frações Contínuas

#26

Made by: Thiago Oliveira

1024MB

0.2s

O pequeno Charles era um dos melhores programadores competitivos do mundo. No entanto, ele nunca gostou muito de programar. Agora que está aposentado, ele pode dedicar seus estudos ao que realmente ama: frações contínuas.

Para se preparar para a próxima Imensa Competição de Phrações Contínuas (ICPC), ele precisa resolver o seguinte problema:

Defina p0 = 1 como a fração de nível 0. Em seguida, defina $ p_1 = \frac{1}{1+1} $ como a fração de nível 1, $p_1$ . Além disso, defina $p2 = \frac{1}{1+\frac{1}{1+1}}$ como a fração de nível 2, $p_2$ , e assim por diante.

Dado um valor inteiro $N$ , ajude Charles a determine o valor do numerador da fração $p_N$.

Input

A primeira e única linha contém um inteiro $N$ $(1 ≤ N ≤ 40)$.

Output

O valor $p_N$ pode ser escrito como uma fração da forma $\frac{a}{b}$ , onde $a$ e $b$ são coprimos. Imprima uma linha contendo o valor de $a$.

Input Example

Output Example