题目描述

给定整数 $A$、$X$、$M$。请计算 $\displaystyle\sum_{i=0}^{X-1} A^i$ 除以 $M$ 的余数。

输入格式

输入以以下格式从标准输入给出。

$A$ $X$ $M$

输出格式

请输出答案。

样例 1

输入

3 4 7

输出

5

样例 2

输入

8 10 9

输出

0

样例 3

输入

1000000000 1000000000000 998244353

输出

919667211

说明/提示

限制条件

• $1 \leq A, M \leq 10^9$
• $1 \leq X \leq 10^{12}$
• 输入均为整数

样例解释 1

$3^0 + 3^1 + 3^2 + 3^3 = 40$。$40$ 除以 $7$ 的余数为 $5$，因此输出 $5$。

由 ChatGPT 4.1 翻译