Periodic points#1820
Computing the number of fixed points and, more generally, the number of periodic orbits within a dynamical system is a question of interest in various fields of research. However, the dynamics may be very complicated even in seemingly simple models. In this task, you are to compute the number of periodic points of period for a piecewise linear map mapping the real interval into itself. That is, given a map f : [0, m] \rightarrow [0, m], you must calculate the number of solutions to the equation f^n(x) = x for x \in [0, m], where f^n denotes the -fold composition of , i.e.
where denotes composition of maps, (gh)(x) = g(h(x)).
Fortunately, the maps in this problem have the following properties:
is a positive integer, and for every integer k \in \{0, 1, \ldots, m\}, is an integer in ; that is, f(k) \in \{0, 1, \ldots, m\}.
For every k \in \{0, 1, \ldots, m-1\}, the map is linear on the interval [k, k+1]. This means that for every x \in [k, k+1], f(x) = (k + 1 - x)f(k) + (x - k)f(k+1), which is equivalent to its graph being a straight line segment on [k, k+1].
Figure 1: Graphs of the third sample map, f_3 (left), and its square, f_3^2 (right).
Since there may be many periodic points, 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 (1 \leq m \leq 80). The next line describes the map ; it contains m+1 integers f(0), f(1), \ldots, f(m), each between and inclusive. The test case ends with a line containing two integers separated by a space: (1 \leq n \leq 5\ 000) and the modulus for the result, (2 \leq \text{mod} \leq 10\ 000).
The input ends with a line containing '0'.
For each test case, output the number of solutions to f^n(x) = x in the interval modulo . If there are infinitely many solutions, print 'Infinity'.
Example 1