Contest Duration: - (local time) (100 minutes) Back to Home
E - Sequence Sum /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

xm で割った余りを f(x,m) と表します。

### 制約

• 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


### 入力例 2

1000 2 16


### 出力例 2

6


### 入力例 3

10000000000 10 99959


### 出力例 3

492443256176507


Score : 500 points

### Problem Statement

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}.

### Constraints

• 1 \leq N \leq 10^{10}
• 0 \leq X < M \leq 10^5
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N X M


### Output

Print \displaystyle{\sum_{i=1}^N A_i}.

### Sample Input 1

6 2 1001


### Sample Output 1

1369


The sequence A begins 2,4,16,256,471,620,\ldots Therefore, the answer is 2+4+16+256+471+620=1369.

### Sample Input 2

1000 2 16


### Sample Output 2

6


The sequence A begins 2,4,0,0,\ldots Therefore, the answer is 6.

### Sample Input 3

10000000000 10 99959


### Sample Output 3

492443256176507