题目描述

给定 $A, X, M$，求 $\Sigma_{i=0}^{X-1}{A^i} \bmod M$

输入格式

一行三个整数 $A, X, M$。

输出格式

一行一个整数，$\Sigma_{i=0}^{X-1}{A^i} \bmod M$

3 4 7

5

8 10 9

0

1000000000 1000000000000 998244353

919667211

数据规模与约定

对于 $30\%$ 的数据，$1\le X\le 1000$。

对于另外 $30\%$ 的数据，$1\le X\le 10^{12}$，$M$ 是质数。

对于 $100\%$ 的数据，$1\le A, M\le 10^9, 1\le X\le 10^{12}$。