Fibonacci Number 2

Interview

Time limit1sMemory limit128 MB

Summary

Compute the nth Fibonacci number for n up to 90.

Level: Easy2 of 10
Topics: Dynamic programming, Math
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 term onward, each Fibonacci number is the sum of the two immediately preceding Fibonacci numbers.

As a formula, 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 natural number n. The value of n is at most 90.

Output

Print the nth Fibonacci number on the first line.

Examples1

Example 1
Input
```
10
```
Expected output
```
55
```