9250: ABC293 —— E - Geometric Progression
[Creator : ]
Description
### Problem Statement
Given integers $A$, $X$, and $M$, find $\displaystyle \sum_{i = 0}^{X-1} A^i$, modulo $M$.
Given integers $A$, $X$, and $M$, find $\displaystyle \sum_{i = 0}^{X-1} A^i$, modulo $M$.
Input
### Input
The input is given from Standard Input in the following format:
```
$A$ $X$ $M$
```
The input is given from Standard Input in the following format:
```
$A$ $X$ $M$
```
Output
### Output
Print the answer.
Print the answer.
Constraints
### Constraints
- $1 \leq A, M \leq 10^9$
- $1 \leq X \leq 10^{12}$
- All values in the input are integers.
- $1 \leq A, M \leq 10^9$
- $1 \leq X \leq 10^{12}$
- All values in the input are integers.
Sample 1 Input
3 4 7
Sample 1 Output
5
$3^0+3^1+3^2+3^3=40$, which equals 5 modulo 7, so 5 should be printed.
Sample 2 Input
8 10 9
Sample 2 Output
0
Sample 3 Input
1000000000 1000000000000 998244353
Sample 3 Output
919667211