Pibonacci

The Fibonacci sequence is defined by the well-known recurrence F[i] = F[i-1] + F[i-2]. This problem uses a slightly modified sequence called the Pibonacci sequence.

The Pibonacci sequence is defined as follows:

• P[n] = 1 for 0 <= n <= pi.
• P[n] = P[n-1] + P[n-pi] otherwise.

Here, n does not have to be an integer while the recurrence is being evaluated. For example, a term such as P[n-pi] may need to be expanded again as P[n-pi-1] + P[n-pi-pi].

Given a natural number n, compute P[n].

The first line contains a natural number n (1 <= n <= 1,000).

Print P[n]. Since the value can be very large, print the remainder after dividing it by 1,000,000,000,000,000,000.