Fibonacci numbers are defined as follows:

• $fib(0) = 0$
• $fib(1) = 1$
• $fib(n) = fib(n-1) + fib(n-2)$ for $n \ge 2$

Task

Write a program that:

• reads an integer $n$ from standard input,
• calculates the $n$-th Fibonacci number ($fib(n)$),
• writes it to standard output.

Input

The first and only line of standard input contains a single integer $n$, $0 \le n \le 40$.

Output

The program should write a single integer equal to $fib(n)$ to standard output.

Examples

Input 1

10

Output 1

55