E - 序列求和

得分：$500$ 分

问题描述

记 $\displaystyle f(x, m)$ 为 $x$ 除以 $m$ 的余数。

设序列 $A$ 的初始值为 $A_1=X$，递推关系式为 $A_{n+1} = f(A_n^2, M)$。 求 $\displaystyle{\sum_{i=1}^N A_i}$。

约束

• $1 \leq N \leq 10^{10}$
• $0 \leq X < M \leq 10^5$
• 所有输入值均为整数。

输入

输入以以下格式从标准输入中给出：

$N$ $X$ $M$

输出

输出 $\displaystyle{\sum_{i=1}^N A_i}$。

6 2 1001

1369

序列 $A$ 为 $2,4,16,256,471,620,\ldots$。因此，答案为 $2+4+16+256+471+620=1369$。

1000 2 16

6

序列 $A$ 为 $2,4,0,0,\ldots$。因此，答案为 $6$。

10000000000 10 99959

492443256176507