피보나치 비스무리한 수열

시간 제한2초메모리 제한512 MB

요약

f(n) = f(n-1) + f(n-3), f(1)=f(2)=f(3)=1인 수열에서 n번째 항을 구한다. n은 116 이하이다.

문제

피보나치 비스무리한 수열은 $f(n) = f(n-1) + f(n-3)$ 으로 정의되는 수열이다. $f(1) = f(2) = f(3) = 1$ 이며, 이 수열을 앞에서부터 나열하면 다음과 같다.

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...

자연수 $n$ 이 주어질 때, 피보나치 비스무리한 수열의 $n$ 번째 수를 구해 보자.

첫째 줄에 자연수 $n$ ( $1 \le n \le 116$ )이 주어진다.

피보나치 비스무리한 수열의 $n$ 번째 수를 출력한다.