Nth Fibonacci Number

An ecologist models a colony where the population in any given month is the two previous months added together. The colony starts empty in month 0 and one pair arrives in month 1. She wants to read off the population for a chosen month.

That sequence is the Fibonacci numbers, pinned here as F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for every later month.

Task: Read a month number and print the population in that month.

Input

A single line holding one integer n, with 0 ≤ n ≤ 50.

Output

One line holding a single integer: F(n).

Example:

Input:
6

Output:
8