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. n f’s z }| { fn = f ◦ .. ◦ f ◦ f, where ◦ stands for the composition of maps, (g ◦ h)(x) = g(h(x)). Fortunately, the maps you will have to work with satisfy some particular properties: • m will be a positive integer and the image of every integer in [0, m] under f is again an integer in [0,m], that is, for every k ∈ {0,1,...,m} we have that f(k) ∈ {0,1,...,m}. • Foreveryk∈{0,1,...,m−1},themapf islinearintheinterval[k,k+1]. Thismeansthatfor every x ∈ [k,k+1], its image satisfies f(x) = (k+1−x)f(k)+(x−k)f(k+1), which is equivalent to its graph on [k, k + 1] being a straight line segment. Figure 1: Graphs of the third map in the sample input, f3 (left), and of its square, f32 (right). Since there might be many periodic points you will have to output the result modulo an integer. Input The input consists of several test cases, separated by single blank lines. Each test case begins with a line containing the integer m (1 ≤ m ≤ 80). 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 (1 ≤ n ≤ 5 000) and the modulus used to compute the result, “mod” (2 ≤ mod ≤ 10 000). The input will finish with a line containing ‘0’. Output 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 Sample Input 2 202 2 10 3 0132 1 137 3 2303 20 10000 0 Sample Output 4 Infinity 9074