eolymp
bolt
Try our new interface for solving problems
Problems

Fibonacci Sequence

Fibonacci Sequence

Time limit 1 second
Memory limit 128 MiB

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 the Fibonacci sequence.

Input data

One positive integer n~(1 \le n \le 40).

Output data

Print the n-th element of the Fibonacci sequence.

Examples

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