a = 129402307
n = gets.to_i
m = gets.to_i
if m == 0
  p 1
  exit
end
n %= a
if n == 0
  p 0
  exit
end
m %= a-1
if m == 0
  p 1
  exit
end
t = 1
while m > 0
  t = t * n % a if m & 1 > 0
  n = n * n % a
  m >>= 1
end
p t