Category

Similar Problems

0711. Fibonacci Sequence

Time limit : 1000 ms
Memory limit : 64 mb

The Fibonacci sequence is defined as follows:

  • a0 = 0
  • a1 = 1
  • ak = ak-1 + ak-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

Input

Output

1

2
1

2

5
5

3

8
21

 

Tayyorladi: Azat Yusupov
Text from: e-olimp.com