A96808.函数求和

我们用函数 $f(x,m)$ 表示 $x$ 除以 $m$ 的余数（也就是 $x$ 对 $m$ 取模）。

给定三个整数 $N,X,M$，定义一个数列 $A$：

• 初始时有 $A_1 = X$；
• 对于每个整数 $i \ge 1$，有

  $$A_{i+1} = f(A_i^2, M).$$

请你计算

$$\sum_{i=1}^N A_i$$

输入包含一行，包含三个整数 $N,X,M$。

输出一个整数，表示

$$\sum_{i=1}^N A_i$$

的值。

数据范围

• $1 \le N \le 10^{10}$；
• $0 \le X < M \le 10^5$；
• 输入中的所有数都是整数。

样例一：

数列 $A$ 为

$$2, 4, 16, 256, 471, 620, \dots$$

所以

$$\sum_{i=1}^6 A_i = 2 + 4 + 16 + 256 + 471 + 620 = 1369.$$

样例二：

数列 $A$ 为

$$2, 4, 0, 0, 0, \dots$$

所以前 $1000$ 项之和为

$$2 + 4 + 0 + \dots + 0 = 6.$$