Pibonacci 2

피보나치 수열은 매우 유명한 수열이며, 점화식은 $F[i] = F[i-1] + F[i-2]$로 표현된다. 이 문제에서는 이를 살짝 변형한 피보나치(Pibonacci) 수열을 다룬다. 점화식은 다음과 같다.

• $P[n] = 1$ (0 ≤ n ≤ π)
• $P[n] = P[n-1] + P[n-π]$ (그 외)

n이 꼭 정수일 필요는 없다. 예를 들어 $P[n-π]$는 $P[n-π-1] + P[n-π-π]$와 같은 식으로 계산해야 한다.

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

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

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