等比数列求和

题目描述

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

输入格式

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

$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

数据范围

• $1 \le A, M \le 10^9$
• $1 \le X \le 10^{12}$
• 输入中的所有值均为整数