The Fibonacci sequence is defined as follows:

• a₀ = 0
• a₁ = 1
• a_k = a_k-1 + a_k-2

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

   Input

   The only positive integer N (1 ≤ N ≤ 40).

   Output

   N-th element of the Fibonacci sequence.

Samples

2

1

5

5

8

21