P0923

周期点

周期点

给定函数 f:[0,m]→[0,m]f:[0,m]\to[0,m]。对于每个整数 kk，其中 0≤k<m0\le k<m，函数 ff 在区间 [k,k+1][k,k+1] 上是线性的，且 f(0),f(1),…,f(m)f(0),f(1),\ldots,f(m) 均为整数。具体地，当 x∈[k,k+1]x\in[k,k+1] 时，有

f(x)=(k+1−x)f(k)+(x−k)f(k+1).f(x)=(k+1-x)f(k)+(x-k)f(k+1).

定义 f1(x)=f(x)f^1(x)=f(x)，对于 n>1n>1，定义

fn(x)=f(fn−1(x)).f^n(x)=f\left(f^{n-1}(x)\right).

给定 f(0),f(1),…,f(m)f(0),f(1),\ldots,f(m)，求方程

fn(x)=xf^n(x)=x

在 x∈[0,m]x\in[0,m] 上的解的个数。若解的个数有限，则答案对给定的模数取模。

本题包含多组测试数据。

输入格式

对于每组测试数据：

第一行输入一个整数 mm。

第二行输入 m+1m+1 个整数，其中第 ii 个整数表示 f(i−1)f(i-1)。

第三行输入两个整数 nn 和 modnum\mathit{modnum}，表示迭代次数以及答案需要取模的模数。

相邻两组测试数据之间可能有一个空行。

当单独输入 m=0m=0 时，表示输入结束。

输出格式

对于每组测试数据，输出一行一个整数，表示方程解的个数对 modnum\mathit{modnum} 取模后的结果。

如果方程有无穷多个解，则输出 Infinity。

样例输入

2
2 0 2
2 10
3
0 1 3 2
1 137
3
2 3 0 3
20 10000

样例输出

4
Infinity
9074

数据范围

  • 1≤m≤801\le m\le 80；
  • 1≤n≤5×1031\le n\le 5\times 10^3；
  • 1≤modnum≤1041\le \mathit{modnum}\le 10^4；
  • 对于所有 0≤i≤m0\le i\le m，均有 0≤f(i)≤m0\le f(i)\le m；
  • 单独输入的 m=0m=0 表示输入结束，不属于任何一组测试数据。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

2
2 0 2
2 10
3
0 1 3 2
1 137
3
2 3 0 3
20 10000

输出

4
Infinity
9074