피보나치 수열

피보나치 수열의 N번째 항을 출력하라. F(1) = 1, F(2) = 1이고 N ≥ 3이면 F(N) = F(N-1) + F(N-2)이다.

입력

첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 40)

출력

피보나치 수열의 N번째 항을 출력한다.

입출력 예시

입력 1

1

출력 1

1

입력 2

6

출력 2

8

설명: 각 예시는 문제의 규칙에 따라 입력을 처리했을 때의 출력이다.