import math, strscans

const m = 10 ^ 7
echo m

let (_, a, n) = stdin.readAll.scanTuple"$i $i"

proc powMod(a, n, x: int): int =
  if n == 1:
    x
  elif n mod 2 == 1:
    powMod(a, n.pred, x * a mod m)
  else:
    powMod(a, n div 2, x ^ 2 mod m)

echo powMod(a, n, a) mod m