Pibonacci

Time limit2sMemory limit128 MB

Summary

Compute a Fibonacci-like sequence defined with the irrational constant pi as a recursive step and output it modulo 10^18.

Level: Medium6 of 10
Topics: Dynamic programming, Recursion, Math
Solved: No attempts yet

Problem

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].

Input

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

Output

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

Examples1

Example 1
Input
```
10
```
Expected output
```
19
```