You might have heard of the Fibonacci numbers and of the number pi. If you let these two ideas merge, a new and esoteric concept comes into being: the Pibonacci numbers. These can be defined for real x>=0 by:
| P(x) = 1 | for 0<=x<4 |
| P(x) = P(x-1) + P(x-pi) | for 4<=x, |
where pi = 3.1415926535... In this problem, you are asked to compute P(x) for a given x.
The input file contains several non-negative real numbers each on a separate line. The last line contains -1 marking the end of the input file.
For each non-negative real number in the input file, output the corresponding Pibonacci number. Should the Pibonacci number be more than 50 digits long, divide it on the consecutive lines, outputting 50 digits on each (the last line may contain less digits).
0 4 11 -1
Output file:
1 2 20
This problem was recently posed by Leonard Schulman and we hope that you will be as charmed by its transcendence as we were.