부분 문제로 나누어 피보나치수 구하기

피보나치수열은 0과 1로 시작하고, 그 뒤의 수는 바로 앞 두 수의 합이다. $n$번째 피보나치수를 부분 문제로 나누어 구하시오.

첫째 줄에 정수 $n$이 주어진다. ($1 \le n \le 90$)

$n$번째 피보나치수를 한 줄에 출력한다. 첫 번째 피보나치수는 0이고, 두 번째 피보나치수는 1이다.