Periodic points |
Computing the number of fixed points and, more generally, the number of periodic orbits within a dynamical system is a question attracting interest from different fields of research. However, dynamics may turn out to be very complicated to describe, even in seemingly simple models. In this task you will be asked to compute the number of periodic points of period n of a piecewise linear map f mapping the real interval [0, m] into itself. That is to say, given a map f : [0, m] [0, m] you have to calculate the number of solutions to the equation fn(x) = x for x [0, m], where fn is the result of iterating function f a total of n times, i.e.
Fortunately, the maps you will have to work with satisfy some particular properties:
Since there might be many periodic points you will have to output the result modulo an integer.
The input consists of several test cases, separated by single blank lines. Each test case begins with a line containing the integer m ( 1m80). The following line describes the map f; it contains the m + 1 integers f (0), f (1),..., f (m), each of them between 0 and m inclusive. The test case ends with a line containing two integers separated by a blank space, n ( 1n5 000) and the modulus used to compute the result, ``mod'' ( 2 mod10 000).
The input will finish with a line containing `0'.
For each case, your program should output the number of solutions to the equation fn(x) = x in the interval [0, m] modulo ``mod''. If there are infinitely many solutions, print `Infinity' instead.
2 2 0 2 2 10 3 0 1 3 2 1 137 3 2 3 0 3 20 10000 0
4 Infinity 9074