eolymp
Competitions

DSA Week 1

Fibonacci Sequence

The Fibonacci sequence is defined as follows:

  • a0 = 0
  • a1 = 1
  • ak = ak-1 + ak-2

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

Input

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

Output

Print the n-th element of the Fibonacci sequence.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2
Output example #1
1
Input example #2
5
Output example #2
5
Input example #3
8
Output example #3
21
Source 2012 All-Ukrainian Collegiate Programming Contest Round I Training Contest, April 19