Given a positive number n, write a program to find nth Fibonacci Number.

Problem Note

• The Fibonacci numbers are the numbers in the following integer sequence : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Example 1

Input: n = 2
Output: 1

Example 2

Input: n = 9
Output: 34