剰余の法 $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)

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)