当前没有测试数据。

E - 等比数列

得分：500 分

问题描述

给定整数 $A$、$X$ 和 $M$，求 $\displaystyle \sum_{i = 0}^{X-1} A^i$ 对 $M$ 取模的结果。

限制

• $1 \leq A, M \leq 10^9$
• $1 \leq X \leq 10^{12}$
• 输入的所有值都是整数。

输入

输入以以下格式从标准输入中给出：

$A$ $X$ $M$

输出

输出答案。

3 4 7

5

$3^0 + 3^1 + 3^2 + 3^3 = 40$，对 $7$ 取模的结果是 $5$，所以应该输出 $5$。

8 10 9

0

1000000000 1000000000000 998244353

919667211