序列求和

题目描述

用 $f(x,m)$ 表示 $x$ 除以 $m$ 的余数。

设数列 $A$ 由初始值 $A_1=X$ 和递推式 $A_{n+1}= f(A_n^2, M)$ 定义。求 $\displaystyle{\sum_{i=1}^N A_i}$。

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

• $1 \leq N \leq 10^{10}$
• $0 \leq X \lt M \leq 10^5$
• 输入均为整数