题目描述

记 $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}$ 的结果。

示例输入 1

6 2 1001

示例输出 1

1369

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

示例输入 2

1000 2 16

示例输出 2

6

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

示例输入 3

10000000000 10 99959

示例输出 3

492443256176507