722. Fibonacci Number

0

Medium

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones. The sequence starts with 0 and 1. Given a number N, calculate the Nth Fibonacci number. Write a solution with a time complexity of O(N).

Input Format

Enter a number N

Output Format

Display the Nth fibonacci

Example

Input

10

Output

55

Constraints

1<=N<=100

Loading...

View Submissions

Console