Mod[(123456789^123456789), 987654321]

PowerMod[123456789, 123456789, 12345]

PowerMod[123456789, 123456789, 987654321]

$RecursionLimit = Infinity;
powermod[a_, 0, p_] := 1
powermod[a_, n_, p_] := 
      Mod[powermod[a, (n/2), p]^2, p] /; EvenQ[n]
powermod[a_, n_, p_] := 
      Mod[powermod[a, n - 1, p]*a, p] /; OddQ[n]

powermod[123456789, 123456789, 987654321]

x = Random[Integer, {(10^199), (10^200)}];
n = Random[Integer, {(10^199), (10^200)}];
p = NextPrime[x];

powermod[x, n, p] // Timing

Mod[powermod[x, p, p] - x, p]

Mod[powermod[x, p - 1, p], p]