Pibonacci

피보나치 수열은 잘 알려진 점화식 F[i] = F[i-1] + F[i-2] 로 정의된다. 이 문제에서는 이를 조금 바꾼 피보나치(Pibonacci) 수열을 다룬다.

피보나치(Pibonacci) 수열은 다음과 같이 정의된다.

• 0 <= n <= pi이면 P[n] = 1이다.
• 그 밖의 경우에는 P[n] = P[n-1] + P[n-pi]이다.

점화식을 계산하는 과정에서 n이 항상 정수일 필요는 없다. 예를 들어 P[n-pi] 같은 항도 필요하다면 P[n-pi-1] + P[n-pi-pi]처럼 다시 전개해서 계산해야 한다.

자연수 n이 주어질 때, P[n]을 구하는 프로그램을 작성하시오.

첫째 줄에 자연수 n (1 <= n <= 1,000)이 주어진다.

첫째 줄에 P[n]을 출력한다. 값이 매우 커질 수 있으므로 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다.