주기점

동역학계의 고정점 개수, 더 일반적으로 주기 궤도의 개수를 계산하는 것은 여러 연구 분야에서 관심을 받는 문제입니다. 하지만 겉보기에는 단순해 보이는 모형에서도 그 동역학은 매우 복잡하게 나타날 수 있습니다. 이 문제에서는 실수 구간 $[0, m]$을 자기 자신으로 보내는 조각별 선형 사상 $f$의 주기 $n$인 주기점의 개수를 세야 합니다. 즉, 사상 $f : [0, m] \rightarrow [0, m]$이 주어질 때, $x \in [0, m]$에 대한 방정식 $f^n(x) = x$의 해의 개수를 구해야 합니다. 여기서 $f^n$은 $f$를 $n$번 반복 합성한 것입니다.

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

$\circ$는 사상의 합성을 뜻하며 $(g \circ h)(x) = g(h(x))$입니다.

이 사상들은 다음 성질을 만족합니다.

• $m$은 양의 정수이고, $f$는 $[0, m]$의 모든 정수를 $[0, m]$의 정수로 보냅니다. 즉, 모든 $k \in \{0, 1, \dots, m\}$에 대해 $f(k) \in \{0, 1, \dots, m\}$입니다.
• 모든 $k \in \{0, 1, \dots, m - 1\}$에 대해 $f$는 구간 $[k, k+1]$에서 선형입니다. 즉, 모든 $x \in [k, k+1]$에 대해 그 상은 $f(x) = (k + 1 - x)\,f(k) + (x - k)\,f(k + 1)$이며, 따라서 $[k, k+1]$에서 $f$의 그래프는 직선 선분입니다.

주기점이 매우 많을 수 있으므로 결과를 주어진 정수로 나눈 나머지를 출력하세요. 해가 무한히 많으면 대신 Infinity를 출력하세요.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 하나의 빈 줄로 구분됩니다. 각 테스트 케이스는 정수 $m$ ($1 \le m \le 80$)이 적힌 줄로 시작합니다. 다음 줄은 사상 $f$를 설명하며, $m + 1$개의 정수 $f(0), f(1), \dots, f(m)$을 담고 있고 각 값은 $0$ 이상 $m$ 이하입니다. 테스트 케이스는 공백으로 구분된 두 정수, 즉 $n$ ($1 \le n \le 5000$)과 나눗셈에 사용할 법 $\mathit{mod}$ ($2 \le \mathit{mod} \le 10000$)가 적힌 줄로 끝납니다.

입력의 끝은 정수 $0$ 하나만 있는 줄로 표시됩니다.

각 테스트 케이스에 대해, 구간 $[0, m]$에서 방정식 $f^n(x) = x$의 해의 개수를 $\mathit{mod}$으로 나눈 나머지를 출력하세요. 해가 무한히 많으면 대신 Infinity를 출력하세요.