9651: ABC179 —— E - Sequence Sum
[Creator : ]
Description
Let us denote by $f(x, m)$ the remainder of the Euclidean division of $x$ by $m$.
Let $A$ be the sequence that is defined by the initial value $A_1=X$ and the recurrence relation $A_{n+1} = f(A_n^2, M)$. Find $\displaystyle{\sum_{i=1}^N A_i}$.
Let $A$ be the sequence that is defined by the initial value $A_1=X$ and the recurrence relation $A_{n+1} = f(A_n^2, M)$. Find $\displaystyle{\sum_{i=1}^N A_i}$.
Input
Input is given from Standard Input in the following format:
```
$N$ $X$ $M$
```
```
$N$ $X$ $M$
```
Output
Print $\displaystyle{\sum_{i=1}^N A_i}$.
Constraints
- $1 \leq N \leq 10^{10}$
- $0 \leq X < M \leq 10^5$
- All values in input are integers.
- $0 \leq X < M \leq 10^5$
- All values in input are integers.
Sample 1 Input
6 2 1001
Sample 1 Output
1369
The sequence A begins 2,4,16,256,471,620,… Therefore, the answer is 2+4+16+256+471+620=1369.
Sample 2 Input
1000 2 16
Sample 2 Output
6
The sequence A begins 2,4,0,0,… Therefore, the answer is 6.
Sample 3 Input
10000000000 10 99959
Sample 3 Output
492443256176507