Nth Fibonacci

Given an integer n, return the nth Fibonacci number.

In mathematics, the Fibonacci numbers, form a sequence called the Fibonacci sequence - In which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1.

To get an nth fibonacci number, you can use the following equation

Equation:

F(n) = F(n-1) + F(n-2)

Example 1

Input

n = 10

Output

Output: 34

Explanation

• The nth fibonacci, in this case, the 10th fibonacci number is calculated as follows.
• first = 0 (According to the definition)
• Second = 1 (According to the definition)
• Third = first + second = 1 + 0 = 1
• Fourth = Third + Second = 1 + 1 = 2
• Fifth = Fourth + Third = 2 + 1 = 3
• Sixth = Fifth + Fourth = 3 + 2 = 5

and so on till...

• Tenth = Ninth + Eighth = 21 + 13 = 34 - This is our solution.

Simple formula is: F(n) = F(n-1) + F(n-2)

Example 2

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Constraints

0 <= n <= 30