피보나치 수 4

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고 1번째 피보나치 수는 1이며, 2번째부터는 바로 앞의 두 피보나치 수를 더한 값이다. 식으로 쓰면 $F_n = F_{n-1} + F_{n-2}$ ($n \ge 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은 10,000보다 작거나 같은 자연수 또는 0이다.

첫째 줄에 n번째 피보나치 수를 출력한다. 값이 64비트 정수에 담기지 않을 만큼 커지므로 임의 정밀도 정수로 계산한다.