Fractions are better when continued

Interview

Time limit1sMemory limit1024 MB

Summary

Given N, print the numerator of p_N, where p_0 = 1 and p_N = 1 / (1 + p_(N-1)), written in lowest terms.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

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$ . Also, $p_2 = \frac{1}{1 + \frac{1}{1+1}}$ is the level $2$ fraction, $p_2$ , and so on.

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

Input

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

Output

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

Examples2

Example 1
Input
```
2
```
Expected output
```
2
```
Example 2
Input
```
10
```
Expected output
```
89
```