Fibonacci Number

Interview

Time limit1sMemory limit128 MB

Summary
Compute the nth Fibonacci number for n up to 45.
Level

Easy1 of 10

Topics
Math, Implementation
Solved
No attempts yet

Problem

The Fibonacci sequence starts with 0 and 1. The 0th Fibonacci number is 0, and the 1st Fibonacci number is 1. From the 2nd number onward, each Fibonacci number is the sum of the two immediately preceding Fibonacci numbers.

In formula form, for n >= 2, F_n = F_{n-1} + F_{n-2}.

The Fibonacci numbers up to n = 17 are as follows.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

Given n, write a program that computes the nth Fibonacci number.

Input

The first line contains a positive integer n. The value of n is at most 45.

Output

Print the nth Fibonacci number on the first line.

Examples1

  1. Example 1

    Input
    10
    Expected output
    55