mod = 129402307
n = readline().to_i % mod
m = readline().to_i
if m == 0
  p 1
elsif n == 0
  p 0
else
  p n.pow(m % (mod - 1), mod)
end