Periodic Points

Computing the number of fixed points, and more generally the number of periodic orbits, of a dynamical system is a question of interest across many fields of research. However, the dynamics can be very complicated to describe, even in seemingly simple models. In this problem you must count the periodic points of period $n$ of a piecewise linear map $f$ that maps the real interval $[0, m]$ into itself. That is, given a map $f : [0, m] \rightarrow [0, m]$, you must compute the number of solutions of the equation $f^n(x) = x$ for $x \in [0, m]$, where $f^n$ is $f$ iterated $n$ times:

$f^n = \underbrace{f \circ \cdots \circ f \circ f}_{n \text{ times}},$

and $\circ$ denotes composition of maps, $(g \circ h)(x) = g(h(x))$.

The maps satisfy the following properties:

• $m$ is a positive integer, and $f$ sends every integer of $[0, m]$ to an integer of $[0, m]$: for every $k \in \{0, 1, \dots, m\}$ we have $f(k) \in \{0, 1, \dots, m\}$.
• For every $k \in \{0, 1, \dots, m - 1\}$, the map $f$ is linear on the interval $[k, k+1]$. That is, for every $x \in [k, k+1]$ its image is $f(x) = (k + 1 - x)\,f(k) + (x - k)\,f(k + 1)$, so the graph of $f$ on $[k, k+1]$ is a straight line segment.

Because there may be many periodic points, output the result modulo a given integer. If there are infinitely many solutions, print Infinity instead.

The input consists of several test cases, separated by single blank lines. Each test case begins with a line containing the integer $m$ ($1 \le m \le 80$). The next line describes the map $f$: it contains the $m + 1$ integers $f(0), f(1), \dots, f(m)$, each between $0$ and $m$ inclusive. The test case ends with a line containing two integers separated by a space: $n$ ($1 \le n \le 5000$) and the modulus $\mathit{mod}$ ($2 \le \mathit{mod} \le 10000$).

The input ends with a line containing a single $0$.

For each test case, output the number of solutions of the equation $f^n(x) = x$ in the interval $[0, m]$, taken modulo $\mathit{mod}$. If there are infinitely many solutions, print Infinity instead.