Problems
Fibonacci Sequence
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 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