Competitions

# Recursion + memorization

# Fibonacci Sequence

The Fibonacci sequence is defined as follows:

`a`

=_{0}**0**`a`

=_{1}**1**`a`

=_{k}`a`

+_{k-1}`a`

_{k-2}

For a given value of **n** find the **n**-th element of an Fibonacci sequence.

#### Input

One positive integer **n** (**1** ≤ **n** ≤ **40**).

#### Output

Print the **n**-th element of the Fibonacci sequence.

Input example #1

2

Output example #1

1

Input example #2

5

Output example #2

5

Input example #3

8

Output example #3

21