Fibonacci Number

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.