피보나치 수열이란 앞의 두 수를 더하여 나오는 수열입니다.

첫 번째 수와 두 번째 수는 모두 1이고, 세 번째 수부터는 이전의 두 수를 더하여 나타냅니다. 피보나치 수열을 나열해 보면 다음과 같습니다.

1, 1, 2, 3, 5, 8, 13 …

자연수 N을 입력받아 N번째 피보나치 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 입력된다.

출력

첫째 줄에 N번째 피보나치 수를 출력한다.

제한 사항

• 1 ≤ N ≤ 40

예제 입력 1

7

예제 출력 1

13