Description

The Fibonacci sequence is defined as follows: the first and second numbers in the sequence are both 1, and each subsequent number is the sum of the two preceding ones. Given a positive integer k, determine the k-th number in the Fibonacci sequence.

Input Format

Input consists of a single line containing a positive integer k. (1 ≤ k ≤ 46)

Output Format

Output a single line containing a positive integer, representing the value of the k-th number in the Fibonacci sequence.

19

4181