Problem Statement

Given integers A, X, and $M, find \displaystyle \sum_{i = 0}^{X-1} A^i, modulo M$.

Input

The input is given from Standard Input in the following format:
A X M

Output

Print the answer.

Constraints

• $1 \leq A, M \leq 10^9$
• $1 \leq X \leq 10^{12}$
• All values in the input are integers.

Sample Input 1

3 4 7

Sample Output 1

5

3^0 + 3^1 + 3^2 + 3^3 = 40, which equals 5 modulo 7, so 5 should be printed.

Sample Input 2

8 10 9

Sample Output 2

0

Sample Input 3

1000000000 1000000000000 998244353

Sample Output 3

919667211

见题面 Input 部分

见题面 Output 部分