피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다.

f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2)

정수를 입력받아, 그에 해당하는 피보나치 수를 출력하는 프로그램을 작성하여라.

입력 형식

출력 형식

예제 입력

100

예제 출력

354224848179261915075

힌트

해당 테스트 데이터의 모든 정답은 1000자를 넘지 않는다. ( f(20) = 6765 이므로 4자다. )