Geometric Progression

题目描述

给定整数 $A, X, M$，求 $\displaystyle \sum_{i = 0}^{X-1} A^i$，模 $M$ 的值。

输入格式

输入按下列格式从标准输入给出： $A$ $X$ $M$

输出格式

输出答案。

3 4 7

5

8 10 9

0

1000000000 1000000000000 998244353

919667211

提示

$1 \leq A, M \leq 10^9$ $1 \leq X \leq 10^{12}$ 输入中的所有值均为整数。$3^0 + 3^1 + 3^2 + 3^3 = 40$，对 $7$ 取模等于 $5$，所以应输出 $5$。

标签: AtCoder|abc293E

来源

AtCoder|abc293E