329. Fibonacci Number

0

Medium

The Fibonacci sequence is a series of numbers where 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. The solution should have 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