피보나치 수

피보나치 수열은 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 2번째 이후의 피보나치 수는 바로 앞의 두 피보나치 수를 더한 값이다.

수식으로 나타내면 n >= 2일 때 F_n = F_{n-1} + F_{n-2}이다.

n = 17까지의 피보나치 수는 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

첫째 줄에 자연수 n이 주어진다. n은 45보다 작거나 같다.

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