피보나치 수

피보나치 수열은 바로 앞의 두 항을 더해 다음 항을 만드는 수열이다. 첫 두 항은 모두 1이다.

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

정수 $n$이 주어질 때, $n$번째 피보나치 수 $f(n)$을 출력하는 프로그램을 작성하여라.

첫째 줄에 정수 $n$ $(1 \le n)$이 주어진다. 입력은 항상 $f(n)$이 1000자리를 넘지 않도록 주어진다.

첫째 줄에 $n$번째 피보나치 수 $f(n)$을 출력한다.

이 문제의 모든 정답은 1000자리를 넘지 않는다. 예를 들어 $f(20) = 6765$으로 4자리다.