local mod = 129402307
local mfl = math.floor

local function bmul(x, y)
  local x1, y1 = mfl(x / 11376), mfl(y / 11376)
  local x0, y0 = x - x1 * 11376, y - y1 * 11376
  return (x1 * y1 * 11069 + (x1 * y0 + x0 * y1) * 11376 + x0 * y0) % mod
end
local function badd(x, y)
  return (x + y) % mod
end

local ns = io.read()
local ms = io.read()

local mul = 1
local n = 0
for i = #ns, 1, -1 do
  local v = ns:sub(i, i):byte() - 48
  n = badd(n, bmul(v, mul))
  mul = bmul(mul, 10)
end
local m = 0
mul = 1
for i = #ms, 1, -1 do
  local v = ms:sub(i, i):byte() - 48
  m = (m + (v * mul) % (mod - 1)) % (mod - 1)
  mul = (mul * 10) % (mod - 1)
end
if ms == "0" then
  print(1)
elseif n == 0 then
  print(0)
else
  local ret = 1
  while 0 < m do
    if m % 2 == 1 then
      ret = bmul(ret, n)
    end
    n = bmul(n, n)
    m = mfl(m / 2)
  end
  print(ret)
end