← All Problems
⏱ 0:00
p-1009

Fibonacci Number

Easy

Given n, print the n-th Fibonacci number where F(0)=0 and F(1)=1.

Input Format

Single integer n

Output Format

Print one integer: F(n).

Constraints

  • 0 <= n <= 45
  • An O(n) iterative solution is recommended

Examples

Input
10
Output
55
Explanation

F(10) = 55.

Hints

Hint 1
Hint 2
>
Input
Expected Output
55
F(10) = 55.

Run uses the currently selected testcase. Submit always evaluates your code against the full hidden test suite from the database.