For any integers p and q with q > 0, define p mod q to be the integer r with 0 <= r <= q −1 such that p−r is divisible by q. For example, we have
109 mod 10 = 9
−7 mod 3 = 2
−56 mod 7 = 0
Let Φ be a function defined recursively as follows.
where a, b, c, d, e, f, g, h are integers with 0 < a, b, c, d, e, f, g, h <= 1000. One can easily see that 0 <= Φ(i) <= 1000 holds for any integer i >= 0. Now for any given integers a, b, c, d, e, f, g, h, i with 0 < a, b, c, d, e, f, g, h, i <= 1000, you are asked to write a program to output
Φ(i). (Hint: a direct recursive implementation of the above recurrence
relation is likely to run forever for large i.)