Fibonacci Number

The Fibonacci sequence is built by adding the previous two terms to obtain the next one. Its first two terms are both 1.

$f(1) = 1, \quad f(2) = 1, \quad f(n) = f(n-1) + f(n-2)\ (n > 2)$

Given an integer $n$, write a program that prints the $n$-th Fibonacci number $f(n)$.

The first line contains an integer $n$ $(1 \le n)$. The input is always chosen so that $f(n)$ has at most 1000 digits.

Print the $n$-th Fibonacci number $f(n)$ on the first line.

Every answer in this problem has at most 1000 digits. For example, $f(20) = 6765$, which has 4 digits.