For this question, you will write a program that generates values from the Fibonacci sequence. The Fibonnaci sequence is recursively defined by:

F_n = F_{n - 1} + F_{n - 2}

Using the following seed values:

F₀ = 0, F₁ = 1

Given a number n, print the nth value of the Fibonacci sequence.

Input:

12

Output:

144

Input:

30

Output:

832040

Each test case will consist of a single positive integer n.

The inputs will always satisfy the following restrictions:

• F_n < 2^32 - 1,
• 0 <= n < 50