剰余の法 \(M\) と互いに素とは限らない数 \(K\) で最後に一度だけ除算を行いたい場合、予め途中の計算を全て \(\bmod MK\) で行えばよいです。

今回求めるものは \(\displaystyle \frac{A^X-1}{A-1}\) なので \(A^X-1\) を \(\bmod (M(A-1))\) で求めればよいです。\(M(A-1)\) は\(10^{18}\) 程度の大きさになるため、計算には多倍長整数(128bit整数)を用いるなどの工夫が必要です。（繰り返し”二倍法”により64bitの範囲で計算することもできます）

\(A=1\) のケースに注意しましょう。

実装例(Python)

A,X,M=map(int,input().split())
if A==1:
  print(X%M)
else:
  print( (pow(A,X,M*(A-1))-1) // (A-1) % M)