AT_abc293_e [ABC293E] Geometric Progression

题目描述

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

输入格式

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

$A$ $X$ $M$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 4 7

输出 #1

5

输入输出样例 #2

输入 #2

8 10 9

输出 #2

0

输入输出样例 #3

输入 #3

1000000000 1000000000000 998244353

输出 #3

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 翻译